Sunday, February 9, 2014

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)

Solution:
DFS transformation question.
Be care of corner cases.


public class Solution {
    public ArrayList restoreIpAddresses(String s) {
        ArrayList result = new ArrayList();
        if(s.length() < 4 || s.length() > 12)
            return result;
            
        helper(s, "", 0, result);
        return result;
    }
    public void helper(String s, String str, int count, ArrayList result){
        if(count == 3 && isValid(s)){
            str += s;
            result.add(str);
        }
        
        for(int i = 1; i <= 3; i++){
            if (s.length() > i){
                String tmp = s.substring(0,i);
                if(isValid(tmp)){
                    helper(s.substring(i), str+tmp+".", count+1, result);
                }
            }
        }
    }
    
    public boolean isValid(String str){
        // check cases like "065"
        if(str.charAt(0) == '0')
            return str.equals("0");
        return Integer.valueOf(str) >= 0 && Integer.valueOf(str) <= 255;
    }
}

No comments:

Post a Comment