2014年4月21日 星期一

[LeetCode] Restore IP Addresses

Problem:
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)
Solution:O(n)
public class Solution {
    public ArrayList restoreIpAddresses(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;
    }
}

沒有留言:

張貼留言