93. Restore IP Addresses产生所有可能的ip地址

［抄题］：

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

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

变量多的时候就一个个看：有单一变量的范围限制，也有多重变量的范围限制。比如新加单词后过长：pos + i > s.length()

［思维问题］：

以为要用backtracing，不知道那样的1到3位怎么加。其实加不了的话就写一般的dfs就行了。

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

.substring方法是小写
需要用到dfs的思想：i从1到3中的一个进去，dfs 还是会for 1到3

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

需要用到dfs的思想：i从1到3中的一个进去，dfs 还是会for 1到3

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public List<String> restoreIpAddresses(String s) {
        //initialization
        List<String> result = new ArrayList<String>();
        
        //corner case
        if (s == null || s.length() > 12) return result;
        
        //generateIpAddresses
        generateIpAddresses(s, 0, 0, "", result);
        
        //return
        return result;
    }
    
    public void generateIpAddresses(String s, int sec, int pos, String curIP, List<String> result) {
        //exit case
        if (sec > 4) return ;

        //add to result if qualified and then return
        if (sec == 4 && pos == s.length()) {
            result.add(curIP);
            return ;
        }

        //add for length from 1 to 3
        for (int i = 1; i <= 3; i++) {
            //necessary exit
            if (pos + i > s.length()) return ;
            String section = s.substring(pos, pos + i);
            //corner case, break
            if ((section.length() > 1 && section.charAt(0) == '0') || Integer.valueOf(section) >= 256) break; 
            //add section to curIP
            generateIpAddresses(s, sec + 1, pos + i, sec == 0 ? section : curIP + "." + section, result);
        }
    }
}

View Code