93 restore ip address

https://leetcode.com/problems/restore-ip-addresses/submissions/

不难 但是edge cases很多，注意最后一个位置是没有点的，所以最后一个segment要特殊检查

注意一下这个用int[]+idx来记录track的方法，比用list要方便的

class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        int[] loc = new int[3];
        dfs(loc, s.toCharArray(), 0, 0, s.length());
        return ans;
    }
    private void dfs(int[] loc, char[] array, int index, int start, int end) {
        if (index == loc.length) {
            int cnt = 0;
            //检查一下最后一段
            if (start < end){
                //防止最后一段开头为0
                if (start + 1 < end && array[start] == '0') return;
                for (int i = start; i < end; i++) {
                    cnt = cnt * 10 + (array[i] - '0');
                    //防止最后overflow了
                    if (cnt >= 256) return;
                }
                if (cnt < 256) ans.add(getIp(loc, array));
            }
            return;
        }
        if (start >= end) return;
        if (array[start] == '0') {
            loc[index] = start;
            dfs(loc, array, index + 1, start + 1, end);
        } else {
            int cnt = 0;
            int i = start;
            while (i < end && cnt < 256) {
                cnt = cnt * 10 + (array[i] - '0');
                // System.out.println(start + " " + cnt);
                loc[index] = i++;
                if (cnt < 256) dfs(loc, array, index + 1, i, end);
            }
        }
    }
    private String getIp(int[] loc, char[] array) {
        char[] ans = new char[array.length + 3];
        int j = 0;
        int idx = 0;
        for (int i = 0; i < array.length; i++) {
            ans[j++] = array[i];
            //防止idx越界
            if (idx < 3 && i == loc[idx]) {
                idx++;
                ans[j++] = '.';
            }
        }
        return new String(ans);
    }
}

可以在最后插一个点来统一一下逻辑，如果最后一个点没插在最后就不要了，这样简单一点，对每个segment规则是如果开头是0那么只能立马进下一层dfs， 否则进dfs到num>255为止

class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, new int[4], 0, s.length(), 0);
        return ans;
    }
    private void dfs(String s, int[] dots, int start, int end, int idx) {
        if (idx == 4) {
        //最后一个点要插在最后
            if (dots[3] != end-1) {
                return;
            }
            String str = build(s, dots);
            if (str == "") {
                return;
            }
            ans.add(str);
            return;
        }
        if (start >= end) {
            return;
        }
        int num = 0;
        for (int i = start; i < end; i++) {
            if (i == start && s.charAt(i) == '0') {
                dots[idx] = i;
                dfs(s, dots, start+1, end, idx+1);
                break;
            } else {
                num = num*10 + (s.charAt(i)-'0');
                if (num > 255) {
                    break;
                }
                dots[idx] = i;
                dfs(s, dots, i+1, end, idx+1);
            }
        }
    }
    private String build(String s, int[] dots) {
        char[] arr = new char[s.length() + 3];
        char[] str = s.toCharArray();
        int idx = 0;
        int ptr = 0;
        for (int i = 0; i < str.length; i++) {
            arr[ptr++] = str[i];
            // 插入到第三个点就好了
            if (idx < 3 && i == dots[idx]) {
                arr[ptr++] = '.';
                idx++;
            }
        }
        return new String(arr);
    }
}