Restore IP Address

RestoreIPAddress.java

/**
 * 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) {
        ArrayList<String> res = new ArrayList<String>();
        if(s == null || s.length() < 4)
            return res;
        String ip = "";
        generate(s, 0, 0, res, ip);
        return res;
    }
    private void generate(String s, int start, int depth, ArrayList<String> res, String ip) {
        int MAX_DEPTH = 4;
        // 3 conditions to stop the dfs
        // too long
        if(s.length() - start > (MAX_DEPTH - depth) * 3) 
            return;
        // too short
        if(s.length() - start < MAX_DEPTH - depth)
            return;
        // found the solution
        if(depth == 4) {
            // remove the "."
            ip = ip.substring(0, ip.length() - 1);
            if(!res.contains(ip))
                res.add(ip);
            return;
        }
        // if none of the conditions above, keep updating the depth
        int num = 0;
        for(int i = start; i < Math.min(start + 3, s.length()); i++) {
            num = num * 10 + (s.charAt(i) - '0');
            if(num <= 255) {
                generate(s, i + 1, depth + 1, res, ip + num + '.');
            }
            // if this depth starts with 0, then we go to the next depth 
            if(num == 0)
                break;
        }
    }
}