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 Solution93 {
    static LinkedList<LinkedList<String>> ans = new LinkedList<LinkedList<String>>();

    public void restoreIpAddresses(String s, LinkedList<String> list3, int n) {
        if (n > 4) {
            return;  //如果分段超過4端就不符合了
        }
        if (s == null || s.equals("*")) {
            LinkedList<String> list1 = new LinkedList<>();
            for (String string : list3) {
                list1.add(string);
            }
            ans.add(list1);
            return;
        }
        for (int i = 1; i < s.length(); i++) {
            String str = s.substring(0, i);
            if (isValid(str)) { //str是否符合理 比如2555就不合理
                list3.add(str);
                String res = s.substring(i, s.length());
                restoreIpAddresses(res, list3, n + 1);
                list3.pollLast();
            }
        }
    }

    private Boolean isValid(String str) {
        if (str.length() > 3 || str.length() <= 0) {
            return false;
        }
        int a = Integer.parseInt(str);
        if (a <= 255 && a > 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String s = "25525511135*";
        LinkedList<String> list3 = new LinkedList<>();
        new Solution93().restoreIpAddresses(s, list3, 0);
        System.out.println(ans);
    }
}