0093.restore-ip-addresses.md

0093.Restore-IP-Addresses

Description

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

Example 1:

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

Tags: Math, String

题意

求2数之和

题解

思路1

直接暴力搜索出所有合法方案。 合法的IP地址由四个0到255的整数组成。我们直接枚举四个整数的位数，然后判断每个数的范围是否在0到255。 时间复杂度分析：一共 nn 个数字，n−1n−1 个数字间隔，相当于从 n−1n−1 个数字间隔中挑3个断点，所以计算量是 O(C3n−1)O(Cn−13)。

func restoreIpAddresses(s string) []string {
    var result []string
    dfs(s, []string{}, &result)
    return result
}

func dfs(s string, temp []string, result *[]string) {
    if len(temp) == 4 && len(s) == 0 {
        *result = append(*result, strings.Join(temp, "."))
        return
    }

    if len(temp) == 4 || len(s) > 3*(4-len(temp)) || len(s) < (4-len(temp)) {
        return
    }

    for i := 1; i <= 3; i++ {
        if i > len(s) {
            continue
        }
        num, _ := strconv.Atoi(s[:i])
        if s[:i] != strconv.Itoa(num) || num > 255 {
            continue
        }

        temp = append(temp, s[:i])
        dfs(s[i:], temp, result)
        temp = temp[:len(temp)-1]
    }
}

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm