Wednesday, February 19, 2014

Leetcode: 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:

We can use backtracking, only we have to be careful on the definition of ip, for instance 10.01.1.1 is not a valid ip. This means any octet has to be a number from 0 to 255 but if it has more than one digit the first one cannot be a zero.

public class Solution {
    public List<String> restoreIpAddresses(String s) 
    {
        List<String> solution = new ArrayList<String>();
        restoreIpAddresses(s, 0, 0, new StringBuilder(), solution);
        return solution;
    }
    
    public void restoreIpAddresses(String s, int index, int octets, StringBuilder sb, List<String> solution) 
    {
        if(octets==4)
        {
            if(index==s.length())
            {
                sb.deleteCharAt(sb.length()-1);
                solution.add(sb.toString());
                sb.append('.');
            }
            return;
        }
        
        for(int size=1; size<=3; size++)
        {
            if(size>1 && s.charAt(index)=='0')
                break;
            if(s.length()-index-size<3-octets)
                break;
            if(Integer.parseInt(s.substring(index,index+size))>255)
                break;
            sb.append(s.substring(index,index+size));
            sb.append('.');
            restoreIpAddresses(s, index+size, octets+1, sb, solution);
            sb.delete(sb.length()-1-size, sb.length());
        }
    }
}

No comments :

Post a Comment