Thinking process

simple process

Mistakes

what's the exist?

corner cases

• "010010"

public class Solution {
    private static final int MAX_NUM = 255;
    private static final int MIN_NUM = 0;
    private static final int  MAX_LENGTH = 3;

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();

        dfsHelper(s, result, new ArrayList<>(), 0, 4);

        return result;
    }

    private void dfsHelper(String s, List<String> result, List<String> list, int start, int depth) {
        //exit

        if (depth < 1 && start >= s.length()) {
            StringBuilder sb = new StringBuilder();
            for (String str : list){
                if (sb.length() != 0) sb.append('.');
                sb.append(str);
            }

            result.add(sb.toString());
            return;
        }

        if (depth < 1 || start >= s.length()) return;

        for (int end = start + 1; end <= start + MAX_LENGTH; ++end) {
            if (end > s.length()) break;
            String subStr = s.substring(start, end);
            if (isValid(subStr)) {
                list.add(subStr);
                dfsHelper(s, result, list, end, depth - 1);
                list.remove(list.size() - 1);
            }
        }
    }

    private boolean isValid(String str) {
        if (str.length() < 1) return false;
        if (str.length() > 1 && str.charAt(0) == '0') return false;

        return Integer.valueOf(str) <= MAX_NUM && Integer.valueOf(str) >= MIN_NUM;
    }
}