LeetCode 93. Restore IP Addresses【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 <= 20
s 仅由数字组成

解法1 DFS+回溯

首先明确一下合法的IP地址的条件：

一个IP地址有四个分段；
每个分段表示的数值小于等于 255 255 255
分段除了表示为 0 0 0 的情况以外，其他情况第一个数字不能为 0 0 0

所以判断分段合法性的代码如下：

stoi(sa) <= 255 && (sa == "0" || seg[0] != '0')

下面的代码，从当前位置的字符开始，往后依次查看长度为 1 , 2 , 3 1,2,3 1,2,3 的字符串，判断它们是否合法，合法则加入IP分段数组，并继续递归。递归回溯后，从IP分段数组中弹出当前分段即可。直到扫描完整个字符串为止，我们判断IP分段数组中是否只有4个分段，是则将分段以 . 连接起来，加入答案中。

为了提升算法的效率，我们可以做一下剪枝：

s s s 如果是合法IP地址，则长度最大只能到 12 12 12 、最小必须 ≥ 4 \ge 4 ≥4 ，题目范围 0 <= s.length <= 3000 这么大，可能是来迷惑人的吧……
递归过程中，如果当前IP分段数组的长度超过了 4 4 4 ，则直接返回，说明之前有分段太小了。

class Solution {
private:
    vector<string> ans; 
    void dfs(const string &s, int idx, vector<string>& addrs) {
        if (addrs.size() > 4) return; // 分段超过4个则剪枝
        if (idx >= s.size()) {
            if (addrs.size() == 4) 
                ans.push_back(addrs[0] + "." + addrs[1] + "." + addrs[2] + "." + addrs[3]);
            return;
        }
        for (int len = 1; len <= 3; ++len) {
            if (idx + len > s.size()) break;
            string sa = s.substr(idx, len); 
            if (stoi(sa) > 255 || (sa != "0" && sa[0] == '0')) break;  
            addrs.push_back(sa);
            dfs(s, idx + len, addrs);
            addrs.pop_back();
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return {};
        vector<string> temp;
        dfs(s, 0, temp);
        return ans;
    }
};

复杂度分析：我们用 SEG_COUNT = 4 \text{SEG\_COUNT} = 4 SEG_COUNT=4 表示IP地址的段数。

时间复杂度： O ( 3 SEG_COUNT × n ) O(3^\text{SEG\_COUNT} \times n) O(3SEG_COUNT×n) 。由于IP地址的每一段的位数不会超过 3 3 3 ，因此在递归的每一层，我们最多只会深入到下一层的 3 3 3 种情况。由于 SEG_COUNT = 4 \text{SEG\_COUNT} = 4 SEG_COUNT=4 ，对应着递归的最大层数，所以递归本身的时间复杂度为 O ( 3 SEG_COUNT ) O(3^\text{SEG\_COUNT}) O(3SEG_COUNT) 。如果我们复原出了一种满足题目要求的IP地址，那么需要 O ( ∣ s ∣ ) = O ( n ) O(|s|) = O(n) O(∣s∣)=O(n) 的时间将其加入答案数组中，因此总时间复杂度为 O ( 3 SEG_COUNT × n ) O(3^\text{SEG\_COUNT} \times n) O(3SEG_COUNT×n) 。
空间复杂度： O ( n ) O(n) O(n) 。 n n n 为 s s s 的长度，但不超过合法IP地址的最大长度。这里不考虑存储答案数组的空间。

解法2 四重循环暴力求解

写的很爽，代码很优雅：

class Solution { 
    public List<String> restoreIpAddresses(String s) {
        List<String> ret = new ArrayList<>();
        StringBuilder ip = new StringBuilder();
        for (int a = 1; a < 4; ++a) {
            for (int b = 1; b < 4; ++b) {
                for (int c = 1; c < 4; ++c) {
                    for (int d = 1; d < 4; ++d) {
                        if (a + b + c + d == s.length()) {
                            int n1 = Integer.parseInt(s.substring(0, a)); // "010" -> 10(int)
                            int n2 = Integer.parseInt(s.substring(a, a + b));
                            int n3 = Integer.parseInt(s.substring(a + b, a + b + c));
                            int n4 = Integer.parseInt(s.substring(a + b + c));
                            if (n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255) {
                                ip.append(n1).append('.').append(n2).append('.').append(n3).append('.').append(n4);
                                if (ip.length() == s.length() + 3) ret.add(ip.toString()); // 有前导零的会被过滤掉
                                ip.delete(0, ip.length());
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
}

复杂度分析：

时间复杂度： O ( 3 4 ) O(3^4) O(34)
空间复杂度： O ( n ) O(n) O(n)

memcpy0