[Leetcode] Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

带有深度限制的DFS题目，递归深度最多为4，使用一个函数来判断当前扫描的字符串是否能构成一个合法的IP地址的部分，合法的字符串要求为：

1. 字符串的长度为1到3
2. 数字不能以0开头，0除外
3. 数字的大小在0~255之间

在递归的时候，如果固定扫描三个字符来减少搜索的范围，需要注意可能产生的越界情况，也可以在不限制扫描三个字符，当某一次判断为false的时候可以直接break出循环，因为当前字符串为后面继续扫描的前缀，已经非法则后面全部非法，这样可以避免越界。总之要非常小心，我就跪在这样的小细节上了。

 public List<String> restoreIpAddresses(String s) {
     List<String> result = new ArrayList<String>();
     dfs(s, "", 0, 3, result);
        return result;
 }
    
    private void dfs(String s, String current, int beg, int cnt, List<String> result) {
        if(cnt == 0) {
            String str = s.substring(beg, s.length());
            if(valid(str)) {
                StringBuffer sb = new StringBuffer(current);
                sb.append(str);
                result.add(sb.toString());
            }
        }
        else {
            for(int i = beg; i < s.length(); i++) {
                String str = s.substring(beg, i+1);
                if(valid(str) == true) {
                    StringBuffer sb = new StringBuffer(current);
                    sb.append(str);
                    sb.append(".");
                    dfs(s, sb.toString(), i+1, cnt-1, result);
                }
                else break; //prefix invalid
            }
        }
    }
    
    private boolean valid(String str) {
        if(str.length() == 1) return true;
        if(str.length() > 3 || str.length() < 1) return false;// the str might be a null string
        if(str.charAt(0) == '0') return false;
        if(Integer.parseInt(str) > 255) return false;
        return true;
    }