复原IP地址

93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

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

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

方法一：暴力

我们枚举三个切割点，将每一段转换为数字，如果都满足 0 ~ 255 则保存最后结果。

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        StringBuffer ip = new StringBuffer();

        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));
                        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) res.add(ip.toString());
                            ip.delete(0, ip.length());
                            }
                        }
                         
                    }
                }
            }
        }
        return res;
    }
}

方法二：回溯

我们使用递归函数 dfs(segId, segStart)表示我们正在从 s[segStart]的位置开始，搜索地址中的 segId 段，其中 segId 取值为 {0, 1, 2, 3}。由于 IP 地址每一段范围为 0 ~ 255 ，我们从 s[segStart] 开始，从小到大枚举这一段 IP 地址的结束位置 segEnd。如果满足要求则进行下一段搜索，递归调用 dfs(segId + 1, segEnd + 1)。

如果某一段中 s[segStart] = ‘0’ ，那么这一段只能为 0。

在递归搜索中，如果四段 IP 地址已经全部得到且遍历完了整个字符串，那么保存结果；如果还没有找到四段 IP 地址但已经遍历完了整个字符串，结束搜索，提前回溯。

class Solution {
    static final int SEG_COUNT = 4;
    List<String> ans = new ArrayList<String>();
    int[] segments = new int[SEG_COUNT];

    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return ans;
    }

    public void dfs(String s, int segId, int segStart){
        //找到 4 段 ip 地址，并且遍历完了字符串，这就是一种答案
        if(segId == SEG_COUNT){
            if(segStart == s.length()){
                StringBuffer ip = new StringBuffer();
                for(int i = 0; i < SEG_COUNT; i++){
                    ip.append(segments[i]);
                    if(i != SEG_COUNT - 1){
                        ip.append('.');
                    }
                }
                ans.add(ip.toString());
            }
            return;
        }
        
        //如果还没找到四段 ip 地址就已经遍历完了字符串，那么提前 回溯
        if(segStart == s.length()){
            return;
        }

        //如果当前数字为 0 ，那么这段 IP 只能为 0
        if(s.charAt(segStart) == '0'){
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        //一般情况
        int addr = 0;
        for(int segEnd = segStart; segEnd < s.length(); ++segEnd){
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if(addr > 0 && addr <= 0xFF){
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            }else{
                break;
            }
        }
    }
}