力扣93：复原IP地址问题解析（Golang实现）

本文将详细解析力扣（LeetCode）平台上的第93题——复原IP地址。此题的核心在于如何从一个仅包含数字的字符串中，通过适当位置插入‘.’来生成所有可能的有效IP地址组合。有效IP地址严格定义为由四个整数构成，每个整数范围在0到255之间，且不包含前导零，各部分之间使用‘.’进行分隔。

例如，“0.1.2.201”和“192.168.1.1”是有效的IP地址，而“0.011.255.245”、“192.168.1.312”和“192.168@1.1”则不符合标准。

题目要求我们根据给定的字符串s，找出所有可能的有效IP地址。需要注意的是，不能改变或重新排列s中的任何数字，仅能通过插入‘.’来分割字符串。

解题思路如下：

1. 每个整数可视为具有三种长度：1位、2位或3位。基于这一特性，可以采用递归方法解决问题。


2. 递归过程中需记录已进行的切分数目，确保总共进行三次切分。当达到第四次切分时，剩余字符串应为空。

下面是具体的Golang代码实现：

func restoreIpAddresses(s string) []string {
    return restore(0, "", s, []string{})
}

func restore(count int, ip, s string, res []string) []string {
    if count == 4 {
        if s == "" {
            res = append(res, ip[:len(ip)-1]) // 去除末尾多余的“.”
        }
        return res
    } else if count <4 {
        if len(s) > 0 {
            res = restore(count+1, ip+s[:1]+".", s[1:], res)
        }
        if len(s) > 1 && s[0] != '0' {
            res = restore(count+1, ip+s[:2]+".", s[2:], res)
        }
        if len(s) > 2 && s[0] != '0' {
            num, _ := strconv.Atoi(s[:3])
            if num <= 255 {
                res = restore(count+1, ip+s[:3]+".", s[3:], res)
            }
        }
    }
    return res
}

在主函数中调用上述函数并测试几个示例：

package main

import (
    "fmt"
    "strconv"
)

func main() {
    fmt.Println(restoreIpAddresses("25525511135"))
    fmt.Println(restoreIpAddresses("0000"))
    fmt.Println(restoreIpAddresses("101023"))
}

运行结果如下：

[255.255.11.135 255.255.111.35]
[0.0.0.0]
[1.0.10.23 1.0.102.3 10.1.0.23 10.10.2.3 101.0.2.3]