复原IP地址

分割字符串的姐妹题

题目：93. 复原 IP 地址 - 力扣（LeetCode）

题解：代码随想录

代码：

class Solution {List<String> res=new ArrayList<>();public List<String> restoreIpAddresses(String s) {if(s.length()>12) return res;backtracking(s,0,0);return res;}public void backtracking(String s,int startIndex,int pointNum){if(pointNum==3){if(check(s,startIndex,s.length()-1)) res.add(s);return;}for(int i=startIndex;i<s.length();i++){if(check(s,startIndex,i)){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);}else{break;}}}public boolean check(String s,int start,int end){if(start>end) return false;if(s.charAt(start)=='0'&&start!=end) return false;int num=0;for(int i=start;i<=end;i++){if(s.charAt(i)<'0'||s.charAt(i)>'9'){return false;}num=num*10+(s.charAt(i)-'0');if(num>255) return false;}return true;}
}

看题解写的，不过是理解了，他与分割字符串的区别就是他多了几个条件

1、分为四段，意味着终止条件变了

2、每一段的一些限制条件，意味着每次循环之前需要进行判断（剪枝）