Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135"
,
return ["255.255.11.135", "255.255.111.35"]
. (Order does not matter)
public class Solution {
public ArrayList<String> restoreIpAddresses(String s) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<String> res = restoreIPAddresses(s,4);
if(res==null) res=new ArrayList<String>();
return res;
}
public ArrayList<String> restoreIPAddresses(String s, int k){
assert(k<=4 && k>=1);
if(s==null||s.length()<k||s.length()>3*k) return null;
ArrayList<String> res = new ArrayList<String>();
for(int i=0; i<Math.min(s.length(),3);i++){
String num = s.substring(0,i+1);
if( (i==0 || num.charAt(0)>'0') && Integer.parseInt(num)<=255){
if(k==1){
if(i==s.length()-1)
res.add(num);
}else{
ArrayList<String> remain = restoreIPAddresses(s.substring(i+1),k-1);
if(remain!=null){
for(String r:remain){
String temp = num+'.'+r;
res.add(temp);
}
}
}
}else
break;
}
return res;
}
}
4 comments:
请问 当 i=0 的时候为什么不进入
ArrayList remain = restoreIPAddresses(s.substring(i+1),k-1);
这里呢 而是 变成i=1 的时候才进去
+Liu Yue 你是说k=1的吧,k=0表示所有数字用完了 要输出一个结果了
不是,是第一次进入的时候k=4 的时候,for里i=0, 往下走 因为不满足k==1, 是不是就应该进入else 里 ramain 那里,不是应该再进入一层么。应为我 没看懂这个 i= 0 的时候怎么走的
Post a Comment