先看一看不用回溯的方法,其实回溯就是用来代替多重for循环的。
这道题由于背景是IP地址,那么限制最多就三轮for循环就可以了,所以不用回溯也可以写出来。
将字符串分为四个子串,然后判断每个子串符不符合要求就可以了,虽然很暴力,但是时间打败了95%,内存打败了76%,也算是还可以的一个方法了。
代码如下:
public ListrestoreIpAddresses(String s) { List ans = new ArrayList<>(); if (s.length() < 4 || s.length() > 12) return ans; for (int i = 1; i <= s.length() && i <= 3; i++) { //切割第一个子串 String s1 = s.substring(0, i); //判断第一个子串符不符合要求 if (s1.length() > 1 && s1.charAt(0) == '0') continue; if (Integer.parseInt(s1)>255) continue; for (int j = i + 1; j <= s.length() && j <= i + 3; j++) { //切割第二个子串并判断 String s2 = s.substring(i, j); if (Integer.parseInt(s2)>255) continue; if (s2.length() > 1 && s2.charAt(0) == '0') continue; for (int k = j + 1; k <= s.length() && k <= j + 3; k++) { //依次判断子串三、四符不符合要求 String s3 = s.substring(j, k); String s4 = s.substring(k); if (s3.length() > 1 && s3.charAt(0) == '0') continue; if (s4.length() > 1 && s4.charAt(0) == '0') continue; if (s4.length() > 3 || s4.length() < 1) continue; if (Integer.parseInt(s3)>255||Integer.parseInt(s4)>255) continue; StringBuilder sb = new StringBuilder(); sb.append(s1); sb.append("."); sb.append(s2); sb.append("."); sb.append(s3); sb.append("."); sb.append(s4); ans.add(sb.toString()); } } } return ans; }
递归的话,模版是分为三步 的:
- 确定参数(字符串s,下个子串的起始位置,当前子串个数)
- 确定终止条件(子串有四个并且字符串遍历结束)
- 确定循环逻辑
递归的代码如下:
class Solution {
List ans = new ArrayList<>();
StringBuilder sb=new StringBuilder();
public List restoreIpAddresses(String s) {
traceback(s,0,0);
return ans;
}
public void traceback(String s,int start,int num){
if (start==s.length()&&num==4){
ans.add(sb.substring(0,sb.length()-1).toString());
return;
}
if (num==4||start==s.length()) return;
for (int i=start+1;i<=s.length()&&i-start<4;i++){
String s1 = s.substring(start, i);
if (!isValid(s1)) break;
sb.append(s1+".");
traceback(s,i,num+1);
sb.delete(sb.length()-s1.length()-1,sb.length());
}
}
public boolean isValid(String s){
if (s.length()<1||s.length()>3||Integer.parseInt(s)>255) return false;
if (s.length()>1&&s.charAt(0)=='0') return false;
return true;
}
}


![[leetCode93 ]复原IP地址(回溯) [leetCode93 ]复原IP地址(回溯)](http://www.mshxw.com/aiimages/31/936406.png)
