【CT】LeetCode手撕—93. 复原 IP 地址

题目

• 原题连接：93. 复原 IP 地址

1- 思路

模式识别：给一个 String 字符串 ——> 复原 IP 地址 ——> 回溯三部曲 ，回溯的切割问题 ——> 实现一个左闭右闭区间的 isValid 实现
回溯三部曲

• 1. 定义回溯参数及返回值
  • public void backTracing(String s ,int startIndex,int pointSum)
  • startIndex ：代表切割线
  • pointSum ：代表 逗点数量
• 2. 回溯终止条件
  • 用一个全局变量 count 来计算逗号的数量，当逗号的数量达到 3 则此时终止
• 3. 回溯逻辑
  • for 中 i 从 startIndex 开始，遍历到 s.length()

IP地址合法性判断

• 1. 不能以 0 开头
• 2. 遍历判断不能是非法字符
• 3. 求和不能大于 255

2- 实现

⭐93. 复原 IP 地址——题解思路

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


    // 回溯
    List<String> res = new ArrayList<>();
    public void backTracing(String s, int startIndex,int pointSum){

        //2. 终止条件
        if(pointSum==3){
            if(isValid(s,startIndex,s.length()-1)){
                res.add(s);
            }
            return;
        }

        //3. 遍历回溯逻辑
        for(int i = startIndex;i<s.length();i++){
            if(isValid(s,startIndex,i)){
                s = s.substring(0,i+1)+"."+s.substring(i+1);
                pointSum++;
                backTracing(s,i+2,pointSum);
                pointSum--;
                s = s.substring(0,i+1)+s.substring(i+2);
            }else{
                break;
            }
        }
    }

    public Boolean isValid(String s,int start,int end){
        if(start>end){
            return false;
        }
        if(start!=end && s.charAt(start)=='0'){
            return false;
        }
        // 遍历判断，字符合法 ，是否超过 255
        int sum = 0;
        for(int i = start;i <= end;i++){
            if(s.charAt(i) >'9' || s.charAt(i) <'0'){
                return false;
            }
            sum = sum*10 + (s.charAt(i)-'0');
            if(sum>255){
                return false;
            }
        }
        return true;
    }
}

3- ACM 实现

public class remakeIP {


    static List<String> res = new ArrayList<>();
    public static List<String> splitIP(String s){
        backTracing(s,0,0);
        return res;
    }

    // 回溯参数及返回值
    public static void backTracing(String s,int startIndex,int pointSum){
        // 2. 终止条件
        if(pointSum==3){
            if(isValid(s,startIndex,s.length()-1)){
                res.add(s);
            }
            return ;
        }

        //3. 回溯
        for(int i = startIndex; i < s.length();i++){
            if(isValid(s,startIndex,i)){
                s = s.substring(0,i+1) + "."+s.substring(i+1);
                pointSum++;
                backTracing(s,i+2,pointSum);
                s = s.substring(0,i+1)+s.substring(i+2);
                pointSum--;
            }else{
                break;
            }
        }
    }


    public static boolean isValid(String s ,int start,int end){
        if(start>end){
            return false;
        }
        // 判断前置 0
        if(start!=end && s.charAt(start)=='0'){
            return false;
        }
        // 遍历判断 非法字符 和 255
        int sum = 0;
        for(int i = start; i <= end;i++){
            if(s.charAt(i)>'9' || s.charAt(i)<'0'){
                return false;
            }
            sum = sum*10+(s.charAt(i)-'0');
            if(sum>255) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("输入字符串s");
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        splitIP(input);
        for(String s : res){
            System.out.println(s+" ");
        }
    }
}