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:O(n)
public class Solution { public ArrayListrestoreIpAddresses(String s) { ArrayList ret = restoreIPAddresses(s,4); if(ret==null) ret=new ArrayList (); return ret; } public ArrayList restoreIPAddresses(String s, int k){ if(s==null||s.length() 3*k) return null; ArrayList ret = new ArrayList<>(); for(int i=0; i'0') && Integer.parseInt(num)<=255){ if(k==1){ if(i==s.length()-1) ret.add(num); }else{ ArrayList remain = restoreIPAddresses(s.substring(i+1),k-1); if(remain!=null){ for(String r:remain){ String temp = num+'.'+r; ret.add(temp); } } } }else break; } return ret; } }
沒有留言:
張貼留言