/*
1. 搜索顺序: 从前到后遍历每个字符, 添加为可能的数值, 如果符合条件就加入结果集中
2. 搜索状态: 
    local: index , cur 
    global : set, buffer, iptable

3. 剪枝:
    单个数字超过255
    数字个数超过4个
    单个数字等于0

4. testcasse:
    0000
    255255255255
    12302550
*/

class Solution {

    static final int IPNUM = 4;
    Set<String> set = new HashSet<>();
    StringBuffer buffer = new StringBuffer();
    int[] iptable = new int[IPNUM];

    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return new ArrayList<String>(set);
    }

    void dfs(String s, int index, int cur){

        if (cur == 4 ) {
            if (index == s.length()) set.add(Arrays.stream(iptable).boxed().map(String::valueOf).collect(Collectors.joining("."))); 
            if (buffer.length() > 0 ) buffer.setLength(buffer.length()-1);
            return;
        }
        if (index >= s.length()) return;

        buffer.append(s.charAt(index));
        int num = Integer.parseInt(buffer.toString());

        if (num > 255){
            buffer.setLength(buffer.length()-1);
            return;
        }

        if(num == 0){
            iptable[cur] = num;
            buffer.setLength(0);
            dfs(s, index + 1, cur + 1);
            return;
        }

        iptable[cur] = num;
        dfs(s, index + 1, cur);
        if (buffer.length() > 0) buffer.setLength(buffer.length()-1);

        iptable[cur] = num;
        buffer.setLength(0);
        dfs(s, index + 1, cur + 1);
        buffer.append(num);
    }
}