LeetCode 93.复原IP地址

思路有效的IP地址是由4个0~255之间的整数组成并且每个整数不能包含前导0。因为我们每次都需要在字符串中间加入.号所以我们可以判断.号的数量如果数量等于3那么就已经分割出来了四个整数那么就可以作为终止条件。为了能够快速排查出不符合条件的情况所以我们每次得到一个整数之后都需要进行判断判断其是否没有前导0并且是否在0~255之间。代码java代码解读复制代码class Solution { ListString result; public ListString restoreIpAddresses(String s) { result new ArrayList(); StringBuilder sb new StringBuilder(s); backtracking(sb,0,0); return result; } public void backtracking(StringBuilder s ,int startIndex, int dotNum){ if(dotNum 3){ if(check(s,startIndex,s.length()-1)){ result.add(s.toString()); return; } } for(int istartIndex;is.length();i){ if(check(s,startIndex,i)){ s.insert(i1,.); dotNum; backtracking(s,i2,dotNum); dotNum--; s.deleteCharAt(i1); }else break; } } //判断每次分割出来的整数是否合法 public boolean check(StringBuilder s, int start,int end){ if(startend) return false; //如果存在前导0那么不合法 if(s.charAt(start)0 start!end) return false; int num0; for(int istart;iend;i){ int temp s.charAt(i)-0; numnum*10temp; if(num255) return false; } return true; } }