Backtracking - 93. Restore IP Addresses

93. Restore IP Addresses

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"]

思路：

题目意思是给一个只包含数字的字符串给出所有合法ip地址的组合。一看就是很典型使用回溯来枚举的题目，使用ip地址每一位值只能是[0, 255]之间的值来剪枝。同时每一位可能有1位或者两位或者三位数字，这样来分别dfs递归求解。

代码：

go：

func restoreIpAddresses(s string) []string {

    var res []string
    if s == "" || len(s) < 4 || len(s) > 12 {
        return res
    }
    
    dfs(&res, s, "", 0)
    
    return res
}

func dfs(res *[]string, s string, temp string, index int) {
    if index == 4 && len(s) == 0 {
        *res = append(*res, temp[1:])
    }
    
    if index == 4 || len(s) == 0 {
        return
    }
    
    // ex:1.1.1.1
    dfs(res, s[1:], temp + "." + s[:1], index+1)
    // ex:11.11.11.11
    if s[0] != '0' && len(s) > 1 {
        dfs(res, s[2:], temp + "." + s[:2], index+1) 
        // ex:111.111. ...
        if len(s) > 2 {
            value, _ := strconv.Atoi(s[:3])
            if value <= 255 {
                dfs(res, s[3:], temp + "." + s[:3], index+1)
            }
        }
    }
    
}