Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

```Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]```

IP address is consist of 4 parts with each part among (0,255)

so every part can be consist of 1, 2 or 3 digits, and the leading one shouldn‘t be zero.

cases:

1. already get 4 parts and index come to the end of the string, add string to the list and return;

2. s.charAt(index)==‘0‘, only one case is valid, that is, this part is "0";

3. iterate through index->index+1, index->index+2, index->index+3 digits, judge whether it is a valid part, if it is, add it to the string, and continue dbp.

```class Solution {
List<String> list=new ArrayList<>();
if(s.length()<4) return list;
findIP(s, list, "", 0, 0);
return list;
}

public void findIP(String s, List<String> list, String str, int index, int part){
if(part==4||index==s.length()){
return;
}
if(s.charAt(index)==‘0‘){
findIP(s, list, str+".0", index+1, part+1);
}
else{
for(int i=1;i<4;i++){
if(index+i<=s.length()&&Integer.parseInt(s.substring(index,index+i))<256){
findIP(s,list, str+"."+s.substring(index,index+i),index+i, part+1);
}
}
}
}
}```

(0)
(0)

0条