Saturday, January 10, 2015

LeetCode 93: 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 {
    private List<String> result;
    private String[] strs; // IP field
    
    public List<String> restoreIpAddresses(String s) {
        // Backtracking problem
        result = new LinkedList<>();
        int len = s.length();
        
        if (len < 3)
            return result;
        
        strs = new String[4];
        
        backTracking(s, 0, 0);
        
        return result;
    }
    
    // startPos --- Start position of IP field
    // cnt --- ID of IP field (0, 1, 2, 3)
    private void backTracking(String s, int startPos, int cnt)
    {
        if (cnt == 4)
        {
            if (startPos == s.length()) // Just use all of the given numbers.
            {
                String ret = strs[0];
                
                for (int i = 1; i < 4; i++)
                {
                    ret += ".";
                    ret += strs[i];
                }
                
                result.add(ret);
            }
        }
        else
        {
            // Note: Avoid overflow.
            for (int i = 1; i<=3 && startPos+i<=s.length(); i++)
            {
                strs[cnt] = s.substring(startPos, startPos+i);
                
                if (place(strs[cnt]))
                    backTracking(s, startPos+i, cnt+1);
            }
        }
        
    }
    
    // Verify if this IP field is qualified or not.
    private boolean place(String str)
    {
        // e.g, "00", "021" are not qualified.
        if (str.length()>1 && str.charAt(0)=='0')
            return false;
            
        if (Integer.parseInt(str) <= 255)
            return true;
        else
            return false;
    }
}

No comments:

Post a Comment