复原ip地址

93. 复原 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 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

解题思路

关键点在于回溯中要通过pointNum判断小数点的数量，pointNum == 3，说明分割完毕，然后判断小数点后的字符串是否合法

代码

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

    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        traversal(sb, 0, 0);
        return ans;
    }

    public void traversal(StringBuilder s, int l, int pointNum){
        if(pointNum == 3){ //小数点为3个，分割完毕
            String sub = s.substring(l);
            if(isValidAdd(sub)){
                ans.add(s.toString());
            }
            return;
        }

        for(int r = l ; r < s.length(); r++){
            String sub = s.substring(l, r + 1);
            if(!isValidAdd(sub)){//不是有效地址,跳过
                continue;
            }
            s.insert(r + 1,'.'); //在最后位置插入小数点
            traversal(s, r + 2, pointNum + 1); //加了小数点,l从r+2开始
            s.deleteCharAt(r + 1); //回溯掉小数点
        }
    }
	
    //判断是否为有效地址
    public boolean isValidAdd(String s){
        if(s.length() == 0){
            return false;
        }
        if(s.length() != 1 && s.charAt(0) == '0' ){
            return false;
        }
        if(s.length() > 3){
            return false;
        }
        int num = Integer.parseInt(s);
        return num <= 255 && num >= 0;
    }
}

不使用StringBuilder的写法

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

    public List<String> restoreIpAddresses(String s) {
          backtracking(s, 0, 0);
          return res;
    }

    public void backtracking(String s, int index, int pointNum){

        if(pointNum==3){//添加了三个逗号，说明分割成4段
            if(index <= s.length()-1 && s.length()-index <= 3){ //然后判断最后一段是否合法,最后一段不能为空且长度小于等于3
                if(isVaildIp(s, index, s.length()-1)){
                     res.add(s);
                }
                   
            }
            return;
        }


        for(int i = index ; i<s.length()&&i-index<3 ;i++){ //剪枝：ip段最大长3
            if(isVaildIp(s,index,i)){ //判断[index,i]这个区间的ip是否合法
               s = s.substring(0,i+1) + "." + s.substring(i+1);
               pointNum++;
               backtracking(s,i+2,pointNum);
               pointNum--;
               s = s.substring(0,i+1) + s.substring(i+2);
            }
        }
    }
    
    
    //判断合法ip
      private boolean isVaildIp(String s, int start, int end) {
        if (s.charAt(start) == '0' && end+1-start>1) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for(int i = start; i<=end; i++){
            if(s.charAt(i)>'9'||s.charAt(i)<'0'){
                return false;
            }
            num = num*10+(s.charAt(i)-'0');
            if(num>255){
                return false;
            }
        }
        num = Integer.parseInt(s.substring(start,end+1));
        if(num<0||num>255){
            return false;
        }
        return true;
    }
}