Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Have you met this question in a real interview?

Yes

Example

Given"25525511135", return

[
  "255.255.11.135",
  "255.255.111.35"
]

Order does not matter.

1. 如果字符串本身小于4或大于12，则不可能组成有效的ip address

public class Solution {
    /*
     * @param s: the IP string
     * @return: All possible valid IP addresses
     */
    public List<String> restoreIpAddresses(String s) {
        // write your code here
        List<String> ans = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return ans;
        }

        List<String> cur = new ArrayList<String>();
        dfs(0, s, cur, ans);
        return ans;
    }

    public void dfs(int startIndex, String s, List<String> cur, List<String> ans) {
        //exit
        if (startIndex >= s.length() && cur.size() == 4) {
            ans.add(getIP(cur));
            return;
        }

        for (int i = startIndex; i < startIndex + 3 && i < s.length(); i++) {
            String current = s.substring(startIndex, i + 1);
            int curVal = Integer.parseInt(current);

            if (curVal > 255) {
                return;
            }

            if (current.length() > 1 && current.charAt(0) == '0') {
                return;
            }

            cur.add(current);
            dfs(i + 1, s, cur, ans);
            cur.remove(cur.size() - 1);

        }
    }

    public String getIP(List<String> cur) {
        String ans = "";
        for (int i = 0; i < cur.size(); i++) {
            ans += cur.get(i) + ".";
        }
        return ans.substring(0, ans.length() - 1);
    }
}