大厂面试题分享 面试题库
前端面试题库 （面试必备） 推荐：★★★★★
地址：前端面试题库
题目描述
Tag : 「回溯」、「DFS」
有效 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：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"] 复制代码
示例 2：
输入：s = "0000" 输出：["0.0.0.0"] 复制代码
示例 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 <= 201<=s.length<=20
s仅由数字组成
回溯算法
和 131. 分割回文串 一样，同样是一道求所有方案的题目，只能是没有太多优化的「爆搜」做法。
设计递归函数为 void dfs(int idx, int n, List<Integer> cur)，其中 idx 和 n 分别代表当前处理字符串 s 的哪个位置，以及字符串 s 的总长度，而 cur 的则是代表子串 s[0 ... (idx - 1)]s[0...(idx−1)] 部分的具体划分方案。
用题目样例 s = "25525511135" 作为 🌰，n 固定为 11，当 idx = 3 时，cur 为 s[0...2] = 255s[0...2]=255 部分的划分方案，cur 可能是 [2,5,5]、[2,55]、[25,5]、[255] 之一，在 cur 的基础上，我们继续爆搜剩余部分，即递归执行 dfs(idx, n, cur)，算法会将剩余部分的划分方案添加到 cur 上，我们只需要确保每次追加到 cur 的数值符合要求即可（没有前导零 且 范围在 [0, 255][0,255] 中）。
在单次回溯过程中，我们可以将 idx 作为当前划分数字的左端点，通过枚举的形式找到右端点 j，并将当前数字 s[idx ... (j - 1)]s[idx...(j−1)] 加到 cur 中（若合法），回溯到底后再添加到 cur 的元素进行移除。
当 idx = n 代表整个 s 已经处理完成，若此时 cur 恰好有 44 个元素，说明我们找到了一组合法方案，将其拼接成字符串追加到答案数组中。同时也是由于划分过程中 cur 最多只有 44 个元素，我们可以用此做简单剪枝。
Java 代码：
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); } } } } 复制代码
Python 代码：
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 代码：
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 } 复制代码
- 时间复杂度：爆搜不讨论时空复杂度
- 空间复杂度：爆搜不讨论时空复杂度
大厂面试题分享 面试题库
前端面试题库 （面试必备） 推荐：★★★★★
地址：前端面试题库
