93. 复原 IP 地址 - 力扣（LeetCode） (leetcode-cn.com)

 

思路：首先拿到题目，可以看作切割问题，将字符串按照一定的规定，将字符串分割成对应的子字符串，考虑使用回溯。

• 组合问题：N个数⾥⾯按⼀定规则找出k个数的集合
• 切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
• ⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
• 排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式
• 棋盘问题：N皇后，解数独等

既然使用回溯，那么重点就在于： 1）决策树怎么画   2）有哪些状态变量  3）题目中涉及到的字符串变量怎么处理（和leetcode51 N皇后有点像，也需要处理字符串）

1、关于决策树怎么画

       可以根据题意，既然最终的结果是需要四段子字符串，那么就想着怎么构造一个四层的决策树，决策树的树枝放的就是"."的数字。

 

2、状态变量

• int layer 用于记录当前是第几个字串
• int begin，记录当前字串是从s的哪个位置开始计算的
• Deque<String> path, 记录某一个结果的路径（可以作为全局变量）

3、如何处理字符串

    这道题可以先将所有的字串给求出来，放入到path中，最后再利用String.join(".", path)用符号"."把path中的元素链接起来

 

class Solution {
       List<String> ans = new ArrayList<>();
    Deque<String> path = new ArrayDeque<>();
    public List<String> restoreIpAddresses(String s) {
 backTrack(0, 0, s);
        return ans;
    }
        public void backTrack(int layer, int begin, String s){
            if(layer==4){
                if(begin == s.length()){
                    ans.add(String.join(".",path));
                }
                return;
            }
            for(int i=begin; i<begin+3; i++){
                if((4-layer)*3 < s.length()-begin){//剩下未分配层数 吃不下 剩余的字母，因为每一层（即每一个字串）最长为3
                    continue;
                }
                if(i > s.length()-1){ // 某一层的字符指针越界了，那么不能再加了，说明后续都不行了
                    break;
                }
                String tmp = s.substring(begin, i+1);
                if(isValid(tmp)){
                    path.add(tmp);
                    backTrack(layer+1, i+1, s);
                    path.removeLast();
                }

            }
    }
  //长度大于1的时候，首字母不能是‘0’, 串不能为空， 长度不可以大于3
    //数值在[0,255]之间
        public boolean isValid(String s) {
        boolean ans = true;
        if((s.length()>1 && s.charAt(0) == '0' || s.isEmpty() || s.length()>3)){
            ans = false;
        }
        int num = Integer.valueOf(s).intValue();
        if(num<0 || num>255){
            ans = false;
        }
        return ans;
    }
}

 

注：关于这个决策树怎么画以、状态变量怎么找、边界状态怎么定这些问题感觉想是想不到的，还是要靠多做，做多了就知道了

       得靠题海战术完事