[Vssue]0093.复原IP地址.md

[youngyangyang04]

https://www.programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

[Du1in9]

class Solution {
    private List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) return result;
        backtracking(s, 0, 0);
        return result;
    }

    private void backtracking(String s, int start, int count) {
        if (count == 3) {
            if (isValid(s, start, s.length() - 1)) result.add(s);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isValid(s, start, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                count++;                        // 1. 处理
                backtracking(s, i + 2, count);  // 2. 递归
                s = s.substring(0, i + 1) + s.substring(i + 2);
                count--;                        // 3. 回溯
            } else {
                break;
            }
        }
    }

    private boolean isValid(String s, int begin, int end) {
        if (begin > end) return false;
        if (s.charAt(begin) == '0' && begin < end) 
            return false;                   // 以 0 开头不合法
        int num = 0;
        for (int i = begin; i <= end; i++) {
            num = num * 10 + (s.charAt(i) - '0');
        }
        return num <= 255;                  // 大于 255 不合法
    }
}

[MayaSHM]

如果将回溯看作抽象树结构，而IP地址一定有四个格子要填数字，那么本体的抽象树深度恒等于5，所以也可以通过传递深度值来作为停止条件的判断。 另一方面，当前层最大可遍历范围也与深度和剩余长度有关，例如"101023"当分割为["10", ".", "10", "."]时，最后两个格子最大长度只能为1。 我认为上述思路的优势在于不用写过于复杂的判断条件，我的python3代码如下

class Solution:
    def __init__(self):
        self.res = []

    def restoreIpAddresses(self, s: str) -> List[str]:
        # 合法的IP地址有4个格子，意味着抽象树深度恒等于4+1
        # 以根节点的深度depth=1来考虑
        self._backtracking(s, [], 0, 1)
        return self.res

    def _backtracking(self, s, path, start, depth):
        # 停止条件：深度=5，且start指向末尾
        if depth == 5:
            if start == len(s):
                # 末尾的”.“不要添加
                self.res.append(''.join(path[:-1]))
            return

        # 每个格子里至少要有一个数字，设当前可循环长度为L, 而剩余格子数 = (5-depth)，剩余长度 = len(s) - L
        # 因此 (len(s)- L) / (5-depth) >= 1，得到L <= len(s) - (5-depth)
        # 由于IP地址最多三个数字，所以最大循环长度length_limit = min(3, L+1)（range左闭右开所以+1）
        # 因此i的取值范围为min(start + length_limit, len(s))
        length_limit = min(3, len(s) - (5 - depth) + 1)
        iter_limit = min(start + length_limit, len(s))
        for i in range(start, iter_limit):
            # 如果第一个值为0，则这个格子只能添加单独的0
            if s[start] == '0' and i - start >= 1:
                break

            # 一个格子里的值不能大于255
            if (i - start == 2 and
                ((s[start] > '2') or
                 (s[start] == '2' and s[start + 1] > '5') or
                 (s[start] >= '2' and s[start + 1] >= '5' and s[start + 2] > '5'))):
                break

            # 处理，分割IP地址字符串
            path.append(s[start: i + 1])
            path.append('.')
            self._backtracking(s, path, i + 1, depth + 1)  # 递归
            # 回溯
            path.pop()
            path.pop()