esc to dismiss

93. 复原 IP 地址

题目

给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "1111"
输出:["1.1.1.1"]

示例 4:

输入:s = "010010"
输出:["0.10.0.10","0.100.1.0"]

示例 5:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

解题思路

这道 字符串算法 题的官方题解是用 回溯,或者说 DFS,但实际上我用 三层循环(暴力算法)性能依然很高。代码也很好理解。

func isValid(s string) bool {
    size := len(s)
    if size == 0 || size > 3 {
        return false
    } else if size > 1 && s[0] == '0' {
        return false
    } else if size == 3 && s[0] > '2' {
        return false
    } else if size == 3 && s[0] == '2' && s[1] > '5' {
        return false
    } else if size == 3 && s[0] == '2' && s[1] == '5' && s[2] > '5' {
        return false
    }

    return true
}

func generateIp(s string, i,j,k int) string {
    var ip strings.Builder
    ip.WriteString(s[0:i])
    ip.WriteRune('.')
    ip.WriteString(s[i:i+j])
    ip.WriteRune('.')
    ip.WriteString(s[i+j:i+j+k])
    ip.WriteRune('.')
    ip.WriteString(s[i+j+k:len(s)])
    return ip.String()
}

func restoreIpAddresses(s string) []string {
    var ips []string
    size := len(s)
    if size < 4 {
        return ips
    }

    for i := 1; i <= 3; i++ {
        if !isValid(s[0:i]) {
            continue
        }
        for j := 1; j <= 3; j++ {
            if i+j > size || !isValid(s[i:i+j]) {
                continue
            }
            for k := 1; k <= 3; k++ {
                if i+j+k >= size || !isValid(s[i+j:i+j+k]) || !isValid(s[i+j+k:size]) {
                    continue
                }

                ips = append(ips, generateIp(s, i, j, k))
            }
        }
    }
    return ips
}

经验教训

略。

x