Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given
Given
"25525511135"
,
return
["255.255.11.135", "255.255.111.35"]
. (Order does not matter)Solution:
We can use backtracking, only we have to be careful on the definition of ip, for instance 10.01.1.1 is not a valid ip. This means any octet has to be a number from 0 to 255 but if it has more than one digit the first one cannot be a zero.public class Solution { public List<String> restoreIpAddresses(String s) { List<String> solution = new ArrayList<String>(); restoreIpAddresses(s, 0, 0, new StringBuilder(), solution); return solution; } public void restoreIpAddresses(String s, int index, int octets, StringBuilder sb, List<String> solution) { if(octets==4) { if(index==s.length()) { sb.deleteCharAt(sb.length()-1); solution.add(sb.toString()); sb.append('.'); } return; } for(int size=1; size<=3; size++) { if(size>1 && s.charAt(index)=='0') break; if(s.length()-index-size<3-octets) break; if(Integer.parseInt(s.substring(index,index+size))>255) break; sb.append(s.substring(index,index+size)); sb.append('.'); restoreIpAddresses(s, index+size, octets+1, sb, solution); sb.delete(sb.length()-1-size, sb.length()); } } }
No comments :
Post a Comment