93. Restore IP Addresses

2ND TRY
Bug free~
1.01.2.5 -> 01 is invalid
so if(i != 0 && num == 0) -> stop exploring
1 notice -> append "." only when sb.length() == 0

Time O(3^4)
depth is 4
each level has 3 subproblems

Space O(4)
System stack

99.63 % 
class Solution {
    public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() < 4 || s.length() > 12) {
return result;
}
dfs(s, 0, 4, new StringBuilder(), result);
return result;
}
// all possible result
private void dfs(String s, int startIndex, int count, StringBuilder sb, List<String> result) {
if (startIndex == s.length() && count == 0) {
result.add(sb.toString());
}
if (startIndex == s.length() || count == 0) {
return;
}
int num = 0;
for (int i = 0; i <= 3 && startIndex + i < s.length(); i++) {
if (i != 0 && num == 0) {
return;
}
num = num * 10 + s.charAt(startIndex + i) - '0';
if (num > 255) {
break;
}
int len = sb.length();
if (len != 0) {
sb.append(".");
}
sb.append(num);
dfs(s, startIndex + i + 1, count - 1, sb, result);
sb.setLength(len);
}
}
}


1ST TRY
这道题简直要搞死我了。。。事实告诉我们，对于这种String表示数字的题，能不转化成数就尽量不要转化成数，否则就是自己给自己刨坑

if (subStr.length() > 1 && subStr.startsWith("0")) break;
可以写成 if (Integer.parseInt(subStr) == 0) break;
当遇到第一个0的时候就break for loop，就不会出现0后面有其他数字的情况了
67.08 %

public class Solution {
    private int PIECE_COUNT = 4; //Assume there's 1 extra dot at the end of the string
    private int MAX_VALUE = 255;
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) return result;
        //TODO
        restoreIpAddressesDfsHelper(s, PIECE_COUNT, 0, new StringBuilder(), result);
        return result;
    }
    private void restoreIpAddressesDfsHelper(String s, int pieceCount, int startIndex, StringBuilder path, List<String> result) {
        if (pieceCount == 0 && startIndex == s.length()) {
            result.add(path.toString());
            return;
        }
        if (startIndex == s.length() || pieceCount == 0) return;
     
        String subStr;
        int pathOriginalLength = 0;
        //at most 3 digits
        for (int offset = 1; offset < 4; offset++) {
            if (startIndex + offset > s.length()) break;
         
            subStr = s.substring(startIndex, startIndex + offset);
            //System.out.println(path);
         
            if (Integer.parseInt(subStr) > MAX_VALUE) break;
            if (subStr.length() > 1 && subStr.startsWith("0")) break;
            pathOriginalLength = path.length();
            path.append(subStr);
            if (pieceCount > 1) path.append('.');
            restoreIpAddressesDfsHelper(s, pieceCount - 1, startIndex + offset, path, result);
            //backtracking
            path.delete(pathOriginalLength, path.length());
        }
    }
}