标题描述

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

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
}
  • 时间复杂度：爆搜不评论时空复杂度
  • 空间复杂度：爆搜不评论时空复杂度

最后

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

在这个系列文章里边，除了讲解解题思路以外，还会尽或许给出最为简练的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的库房：github.com/SharingSour… 。

在库房地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更抢手的「书面考试/面试」相关资料可拜访排版精巧的 合集新基地