复原IP地址

93. 复原 IP 地址

难度中等569

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 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 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 0 <= s.length <= 3000
• s 仅由数字组成

回溯

关键点：

• 注意不能含有前导0
• 每一个域的值不能大于255
• 中间点的数量应该是三
• StringBuilder到最后赋值的时候不能删除字符，否则返回上一层回溯的过程就不正确了

class Solution {
    public List<String> restoreIpAddresses(String s) {
        if(s.length()>12)return list;
        dfs(s,0,0);
        return list;
    }

    List<String> list = new ArrayList<>();
    StringBuilder bd = new StringBuilder();
    // count用来计数点的数量,最终点的数量应该是3
    public void dfs(String s,int index,int count){
        // 因为是下一次循环,这里应该写成4
        if(index==s.length()&&count==4){
            String temp = bd.toString();
            temp = temp.substring(0,temp.length()-1);
            list.add(temp);
            return;
        }
        
        for(int i=index+1;i<=index+3&&i<=s.length();i++){
            String temp = s.substring(index,i);
            // 判断是否大于255
            if(Integer.parseInt(temp)>255)continue;
            // 不能以0开头并且当前的字符不是0
            if(temp.startsWith("0")&&temp.length()>1)continue;
            count++;
            bd.append(temp);
            bd.append(".");
            dfs(s,i,count);
            count--;
            bd.deleteCharAt(bd.length()-1);
            bd.delete(bd.length()-temp.length(),bd.length());
        }
    }
}

赏

谢谢你请我吃糖果

微信