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 {
    public List<String> restoreIpAddresses(String s) {
        List<Integer> arr = new ArrayList<Integer>();
        for (char ch : s.toCharArray()) arr.add((int)(ch - '0'));
        List<List<Integer>> res = restoreIPHelper(arr, 0, new ArrayList<Integer>(), new ArrayList<List<Integer>>());
        List<String> strList = new ArrayList<String>();
        for (List<Integer> list : res) {
            String temp = new String();
            temp=list.get(0).toString();
            for (int i = 1; i < list.size(); i++) {
                temp += ".";
                temp += list.get(i);
            }
            strList.add(temp);
        }
        return strList;
    }
    public List<List<Integer>> restoreIPHelper(List<Integer> arr, int start, List<Integer> soFar, List<List<Integer>> res){
        if (start == arr.size() && soFar.size() == 4) {
            res.add(soFar);
            return res;
        }
        if (start >= arr.size() || soFar.size() > 4 || start - (4 - soFar.size()) * 3 >= arr.size()) {
            return res;
        }
        int temp = arr.get(start);
        soFar.add(temp);
        res = restoreIPHelper(arr, start+1, new ArrayList<Integer>(soFar), res);
        soFar.remove(soFar.size() - 1);
        if (temp == 0) {
            return res;
        }
        if (start + 1 >= arr.size()) return res;
        temp = temp * 10 + arr.get(start + 1);
        soFar.add(temp);
        res = restoreIPHelper(arr, start + 2, new ArrayList<Integer>(soFar), res);
        soFar.remove(soFar.size() - 1);
        if (start + 2 >= arr.size()) return res;
        temp = temp * 10 + arr.get(start + 2);
        if (temp < 256){
            soFar.add(temp);
            res = restoreIPHelper(arr, start + 3, new ArrayList<Integer>(soFar), res);
        }
        return res;
    }
}

huimeich / leetcode-solution

93. Restore IP Addresses #129