请教Restore IP Addresses题

楼主每当遇到recursion题，跑test case的时候，基本上都会绕晕。不知道各位大神有什么理清recursion思路的建议。比如这道restore IP addresses的题，在网上找到了如下code解法：

1. class Solution {
   
2.     public List<String> restoreIpAddresses(String s) {
   
3.         List<String> res = new ArrayList<String>();
   
4.         helper(s, 0, "", res);
   
5.         return res;   
   
6.     }
   
7.     public void helper(String s, int n, String out, List<String> res){
   
8.         if(n == 4){
   
9.             if(s.isEmpty()) res.add(out);
   
10.             return;
    
11.         }
    
12.         for(int k = 1; k < 4; k++){
    
13.             if(s.length() < k) break;
    
14.             int val = Integer.parseInt(s.substring(0,k));
    
15.             if(val > 255 || k != String.valueOf(val).length()) continue;
    
16.             helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3? "": "."), res);
    
17.         }
    
18.     }
    
19. }

复制代码

对于第15行中的k != String.valueOf(val).length()条件，实在想不明白，请大家指点一下这个条件的作用。

这个k != String.valueOf(val).length() 是为了当prefix 0 存在的时候。防止加上duplicate的ip。
比如10111，分开可以分开成1:1:1:1,但是如果没这个条件，会存在多个这样的ip.因为他是来自于1:01:1:1。

有用给我加米啊

递归的题目建议画树状图理清思路，节点是状态，边是动作，递归就是深度+1，回溯就是深度-1。
这题从根结点空字符串开始，每次选择合法的1个或2个或3个数字构造ip地址，因为ip地址由4个整数组成，所以限定深度为4，当深度刚好为4且当前构造的ip地址与题目给的相符，结束DFS。

randallhong 发表于 2020-2-14 14:18
这个k != String.valueOf(val).length() 是为了当prefix 0 存在的时候。防止加上duplicate的ip。
比如1011 ...

谢谢解答，就是说Integer.parseInt()会把“01”，变成1，用k!=String.valueOf(val).length()跳过这种情况是吗

小水 发表于 2020-2-14 11:44
谢谢解答，就是说Integer.parseInt()会把“01”，变成1，用k!=String.valueOf(val).length()跳过这种情况 ...

这句话就是防止这种情况，“01”不合规则，不可以变成“1”。这句话也可以写成：

String s1 = s.substring(0,k);
if (val >255 || (s1.length() >1 and s1.charAt(0) == '0')) continue;