Leetcode 93 复原IP地址

Leetcode 93 复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

链接：https://leetcode.cn/problems/restore-ip-addresses

解题思路：

使用回溯法
终止条件： ①当分段已满4段 or ②字符串已分配完
若①②均满足则说明该IP合法，加入结果集，再返回
若只满足两者其一，说明该IP不合法，直接返回
单层递归： 判断一段该如何划分，输入参数（字符串s，该段开始位置start，已分段落数number）
判断一段是否合法（长度，数值大小，首位是否为0）
①分段长度（i + 1 - start）<= 3
②数值大小在[0,255]范围内
③若该段长度大于1 且 该段首为0
判断完毕添加该段，再判断是否需要添加小数点，已分段落数++进入下一分段递归
撤销添加分段的操作，已分段落数--，在判断是否需要删除小数点，删除该分段

class Solution {
    List<String> res = new LinkedList<>();
    StringBuilder path = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return res;
    }
    private void dfs(String s, int start, int number) {
        // 终止条件
        if (number == 4 && start == s.length()) {
            res.add(path.toString());
            return;
        }
        if (number == 4 || start == s.length()) {
            return;
        }
        // 单层递归
        for (int i = start; i < s.length(); i++) {
            if (i - start >= 3) {
                break;
            }
            if (Integer.parseInt(s.substring(start, i + 1)) < 0 || Integer.parseInt(s.substring(start, i + 1)) > 255) {
                break;
            }
            if (i > start && s.charAt(start) == '0') {
                break;
            }
            // 处理逻辑
            path.append(s.substring(start, i + 1));
            number++;
            if (number <= 3) {
                path.append(".");
            }
            // 递归
            dfs(s, i + 1, number);
            // 撤销处理
            if (number <= 3) {
                path.deleteCharAt(path.length() - 1);
            }
            number--;
            path.delete(path.length() - (i - start + 1), path.length());
        }
    }
}