0093. 复原 IP 地址【中等】
1. 📝 题目描述
有效 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。
- 例如:
"0.1.2.201"和"192.168.1.1"是有效 IP 地址,但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是无效 IP 地址。
给定一个只包含数字的字符串 s,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。
示例 1:
txt
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]1
2
2
示例 2:
txt
输入:s = "0000"
输出:["0.0.0.0"]1
2
2
示例 3:
txt
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]1
2
2
提示:
1 <= s.length <= 20s仅由数字组成
2. 🎯 s.1 - 回溯
c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void dfs(char* s, int start, int seg, char segments[][4], char** result, int* returnSize) {
if (seg == 4 && start == (int)strlen(s)) {
char* ip = (char*)malloc(16);
sprintf(ip, "%s.%s.%s.%s", segments[0], segments[1], segments[2], segments[3]);
result[(*returnSize)++] = ip;
return;
}
if (seg == 4 || start == (int)strlen(s)) return;
for (int len = 1; len <= 3 && start + len <= (int)strlen(s); len++) {
if (len > 1 && s[start] == '0') break; // 禁止前导零
char part[4] = {0};
strncpy(part, s + start, len);
if (atoi(part) > 255) break;
strcpy(segments[seg], part);
dfs(s, start + len, seg + 1, segments, result, returnSize);
}
}
char** restoreIpAddresses(char* s, int* returnSize) {
*returnSize = 0;
char** result = (char**)malloc(sizeof(char*) * 256);
char segments[4][4];
dfs(s, 0, 0, segments, result, returnSize);
return result;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
js
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function (s) {
const result = []
const dfs = (start, seg, path) => {
if (seg === 4 && start === s.length) {
result.push(path.join('.'))
return
}
if (seg === 4 || start === s.length) return
for (let len = 1; len <= 3 && start + len <= s.length; len++) {
if (len > 1 && s[start] === '0') break // 禁止前导零
const part = s.substring(start, start + len)
if (Number(part) > 255) break
path.push(part)
dfs(start + len, seg + 1, path)
path.pop()
}
}
dfs(0, 0, [])
return result
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
py
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
result = []
def dfs(start: int, seg: int, path: list):
if seg == 4 and start == len(s): result.append('.'.join(path)); return
if seg == 4 or start == len(s): return
for length in range(1, 4):
if start + length > len(s): break
if length > 1 and s[start] == '0': break # 禁止前导零
part = s[start:start + length]
if int(part) > 255: break
path.append(part)
dfs(start + length, seg + 1, path)
path.pop()
dfs(0, 0, [])
return result1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
- 时间复杂度:
,每段最多取 3 个字符,最多 4 段 - 空间复杂度:
,递归栈深度最多 4 层,加上输出字符串
算法思路:
- 回溯尝试将字符串分为 4 段,每段长度 1–3
- 剪枝条件:数值超过 255 或存在前导零时直接跳过
- 当恋好分为 4 段且所有字符恰好用完时,用
'.'拼接加入结果