LC 93. 复原 IP 地址

题目描述

这是 LeetCode 上的 93. 复原 IP 地址 ,难度为 中等

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 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:

1
2
3
输入:s = "25525511135"

输出:["255.255.11.135","255.255.111.35"]

示例 2:
1
2
3
输入:s = "0000"

输出:["0.0.0.0"]

示例 3:
1
2
3
输入:s = "101023"

输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • $1 <= s.length <= 20$
  • s 仅由数字组成

回溯算法

131. 分割回文串 一样,同样是一道求所有方案的题目,只能是没有太多优化的「爆搜」做法。

设计递归函数 void dfs(int idx, int n, List<Integer> cur),其中 idx 代表当前处理字符串 s 的哪个位置,n 代表字符串 s 总长度,而 cur 的则是代表子串 $s[0 … (idx - 1)]$ 部分的具体划分方案。

用题目样例 s = "25525511135" 作为 🌰,n 固定为 11

idx = 3 时,cur 为 $s[0…2] = 255$,cur 部分的划分方案可能是 [2,5,5][2,55][25,5][255] 之一。

cur 的基础上,我们继续爆搜剩余部分,即递归执行 dfs(idx, n, cur),算法会将剩余部分的划分方案添加到 cur 上,我们只需要确保每次追加到 cur 的数值符合要求即可(没有前导零 且 范围在 $[0, 255]$ 中)。

在单次回溯过程中,我们可以将 idx 作为当前划分数字的左端点,通过枚举的形式找到右端点 j,并将当前数字 $s[idx … (j - 1)]$ 加到 cur 中(若合法),回溯到底后再添加到 cur 的元素进行移除。

idx = n 代表整个 s 已经处理完成,若此时 cur 恰好有 $4$ 个元素,说明我们找到了一组合法方案,将其拼接成字符串追加到答案数组中。

同时也是由于划分过程中 cur 最多只有 $4$ 个元素,我们可以用此做简单剪枝。

Java 代码:

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
class Solution {
List<String> ans = new ArrayList<>();
char[] cs;
public List<String> restoreIpAddresses(String s) {
cs = s.toCharArray();
dfs(0, cs.length, new ArrayList<>());
return ans;
}
void dfs(int idx, int n, List<Integer> cur) {
if (cur.size() > 4) return ;
if (idx == n) {
if (cur.size() == 4) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 4; i++) sb.append(cur.get(i)).append(".");
ans.add(sb.substring(0, sb.length() - 1));
}
} else {
for (int i = idx; i < n; i++) {
int t = 0;
for (int j = idx; j <= i; j++) t = t * 10 + (cs[j] - '0');
if (cs[idx] == '0' && i != idx) break;
if (t > 255) break;
cur.add(t);
dfs(i + 1, n, cur);
cur.remove(cur.size() - 1);
}
}
}
}

C++ 代码:
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
30
31
class Solution {
public:
vector<string> ans;
string s;
void dfs(int idx, int n, vector<int>& cur) {
if (cur.size() > 4) return ;
if (idx == n) {
if (cur.size() == 4) {
string sb;
for (int i = 0; i < 4; i++) sb += to_string(cur[i]) + ".";
ans.push_back(sb.substr(0, sb.length() - 1));
}
} else {
for (int i = idx; i < n; i++) {
int t = 0;
for (int j = idx; j <= i; j++) t = t * 10 + (s[j] - '0');
if (s[idx] == '0' && i != idx) break;
if (t > 255) break;
cur.push_back(t);
dfs(i + 1, n, cur);
cur.pop_back();
}
}
}
vector<string> restoreIpAddresses(string _s) {
s = _s;
vector<int> cur;
dfs(0, s.length(), cur);
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
ans = []
def dfs(idx, n, cur):
if len(cur) > 4:
return
if idx == n:
if len(cur) == 4:
ans.append('.'.join(cur))
else:
for i in range(idx, n):
t = 0
for j in range(idx, i + 1):
t = t * 10 + (ord(s[j]) - ord('0'))
if s[idx] == '0' and i != idx:
break
if t > 255:
break
cur.append(str(t))
dfs(i + 1, n, cur)
cur.pop()
dfs(0, len(s), [])
return ans

TypeScript 代码:
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
function restoreIpAddresses(s: string): string[] {
const ans = new Array<string>()
function dfs(idx: number, n: number, cur: Array<number>): void {
if (cur.length > 4) return
if (idx == n) {
if (cur.length == 4) {
let str = ''
for (let i = 0; i < 4; i++) str += cur[i] + "."
ans.push(str.substring(0, str.length - 1))
}
} else {
for (let i = idx; i < n; i++) {
let t = 0
for (let j = idx; j <= i; j++) t = t * 10 + (s.charCodeAt(j) - '0'.charCodeAt(0))
if (s[idx] == '0' && i != idx) break
if (t > 255) break
cur.push(t)
dfs(i + 1, n, cur)
cur.pop()
}
}
}
dfs(0, s.length, new Array<number>())
return ans
}

  • 时间复杂度:爆搜不讨论时空复杂度
  • 空间复杂度:爆搜不讨论时空复杂度

最后

这是我们「刷穿 LeetCode」系列文章的第 No.93 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!