import java.util.ArrayList;
import java.util.List;

public class _93 {
    static class Solution1 {
        public List<String> restoreIpAddresses(String s) {
            //别人的暴力破解思路
            List<String> res = new ArrayList<>();
            for (int a = 1; a <= 3; a++)
                for (int b = 1; b <= 3; b++)
                    for (int c = 1; c <= 3; c++)
                        for (int d = 1; d <= 3; d++) {
                            if (a + b + c + d == s.length()) {
                                StringBuilder sb = new StringBuilder();
                                int x1 = Integer.parseInt(s.substring(0, a));
                                int x2 = Integer.parseInt(s.substring(a, a + b));
                                int x3 = Integer.parseInt(s.substring(a + b, a + b + c));
                                int x4 = Integer.parseInt(s.substring(a + b + c, a + b + c + d));
                                if (x1 > 255 || x2 > 255 || x3 > 255 || x4 > 255) continue;
                                sb.append(x1).append('.')
                                        .append(x2).append('.')
                                        .append(x3).append('.')
                                        .append(x4);
                                //校验,防止以0开头长度大于1的数字出现
                                if (sb.length() == s.length() + 3) res.add(sb.toString());
                            }
                        }
            return res;
        }
    }

    static class Solution2 {
        class Solution {
            public List<String> restoreIpAddresses(String s) {
                List<String> res = new ArrayList<>();
                if (s.length() > 12) return res;
                dfs(res, s.toCharArray(), new ArrayList<>(), 0);
                return res;
            }

            public void dfs(List<String> res, char[] s, List<String> path, int idx) {
                if (path.size() == 4) {
                    if (idx != s.length) return;
                    StringBuilder sb = new StringBuilder();
                    for (int x = 0; x < path.size(); x++) {
                        if (x != 0) {
                            sb.append('.');
                        }
                        sb.append(path.get(x));
                    }
                    res.add(sb.toString());
                    return;
                }
                int cur = 0;
                for (int i = idx; i < s.length && cur <= 255; i++) {
                    int val = s[i] - '0';
                    if (val == 0 && cur == 0) {
                        path.add(Integer.toString(cur));
                        dfs(res, s, path, i + 1);
                        path.remove(path.size() - 1);
                        break;
                    } else {
                        cur = cur * 10 + val;
                        if (cur <= 255) {
                            path.add(Integer.toString(cur));
                            dfs(res, s, path, i + 1);
                            path.remove(path.size() - 1);
                        }
                    }
                }
            }
        }
    }
}