93.复原IP地址

题解

​ 因为要找出所有可行的ip地址，我们需要选择个位数、十位数、小于255的百位数(十六进制的0XFF)分别遍历。因为后续操作十分类似，我们可以选择使用递归。

• 当遍历到了字符串末尾，操作完成。
• 当ip地址的四段都已确定，而字符串还未遍历完，操作完成。
• 当下一字符为0，后一段ip只能为单一的0。
• 当选择的数超过255，for循环中必须break。

class Solution {
    List<String> res = new LinkedList<>();	// 结果
    public List<String> restoreIpAddresses(String s) {
        int[] segments = new int[4];
        backtrack(s, 0, 0, segments);
        return res;
    }

    public void backtrack(String s, int start, int segmentNum, int[] segments) {
        // 到达结束条件
        if (segmentNum == 4) {
            if (start == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 3; i++) {
                    sb.append(segments[i]).append(".");
                }
                sb.append(segments[3]);
                res.add(sb.toString());
            }
            return;
        }

        // 提前回溯
        if (start == s.length()) {
            return;
        }

        // 约束条件，0开头，特别处理
        if (s.charAt(start) == '0') {
            segments[segmentNum] = 0;
            backtrack(s, start + 1, segmentNum + 1, segments);
        }

        int temp = 0;
        for (int end = start; end < s.length(); end++) {
            // 做选择
            temp = temp * 10 + (s.charAt(end) - '0');
            if (temp > 0 && temp <= 255) {
                segments[segmentNum] = temp;
                backtrack(s, end + 1, segmentNum + 1, segments);
            } else {    // 这个break极为重要，没有的话会产生错误答案
                break;
            }
        }
    }
}

本文地址：https://blog.csdn.net/Rush6666/article/details/107900746