刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/restore-ip-addresses/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

有效 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址 ，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

思路

IP地址我们都很熟悉不过了

• 0-255之间
• 不能有前导0

那么这个问题其实就是，如何切分s，使得切分结果能够满足IP地址的要求了
每一节都应该是一个相似的处理逻辑：

• 从头部开始取值，是0则只可能是本节仅为0否则就违反了不能有前导0的要求
• 逐步增加位数，直到所组成数字大于255，则此时得到的结果集为本节所有的可能解，但是否真的可行，还要看后续节的分隔情况
• 最后一节有些特殊，那就是剩下的字符必须全部归属本节，所以最后一节不用考虑分隔，也就是循环的退出逻辑了

至此，上代码

代码

func restoreIpAddresses(s string) []string {
	res := getIp(s, 0, 1)
	return res
}

func getIp(s string, startP, no int) []string {
	// 最后一节只有一种可能，如果0开头则直接放弃
	if no == 4 {
		if s[startP] == '0' && startP != len(s)-1 {
			return []string{}
		}
		lastNum := 0
		for i := startP; i <= len(s)-1; i++ {
			num := int(s[i] - '0')
			lastNum = lastNum*10 + num
		}
		// 结果值超过255则直接放弃
		if lastNum > 255 {
			return []string{}
		} else {
			return []string{strconv.Itoa(lastNum)}
		}
	}
	thisPartNum := 0
	strs := make([]string, 0)
	for i := startP; i <= len(s)-1-4+no; i++ {
		num := int(s[i] - '0')
		// 特殊情况，0
		if num == 0 && thisPartNum == 0 {
			strs = append(strs, strconv.Itoa(thisPartNum))
			break
		// 超过255弃掉
		} else if thisPartNum*10+num > 255 {
			break
		// 其他的为可能结果
		} else {
			thisPartNum = thisPartNum*10 + num
			strs = append(strs, strconv.Itoa(thisPartNum))
		}
	}
	res := make([]string, 0)
	// 遍历可能结果，找下一节
	for _, str := range strs {
		temps := getIp(s, startP+len(str), no+1)
		for _, temp := range temps {
			res = append(res, str+"."+temp)
		}
	}
	return res
}