题意

一个有效的IP地址正好由四个整数组成，由单点分隔。每个整数在0和255之间（包括），不能有前导零。

例如，"0.1.2.201 "和 "192.168.1.1 "是有效的IP地址，但 "0.011.255.245"、"192.168.1.312 "和 "[email protected] "是无效的IP地址。 给定一个只包含数字的字符串s，返回所有可能的有效IP地址，这些地址可以通过在s中插入点来形成。你不允许重新排序或删除s中的任何数字。

思路

这道题主要关注的就是前导零，以及不能超过255的问题。

• 对于022这种情况，只能是0.22, 0.2.2这样，02是不合法的。
• 再就是3456对于这个，我们可以是34.56，3.45.6，34.5.6等，但是345.6就是非法的了，ip的合法范围是0-255
• . 的数量，合法的ip只有3个.。

所以根据上述条件，我们可以从下标0开始，看他可以组成的数字，然后再判断余下的，就是一个递归了。

func restoreIpAddresses2(s string) []string {
	ans := make([]string, 0)
	var dfs func(int, int, string)
	dfs = func(start, dot int, prefix string) {
		if start >= len(s) {
			return
		}
		if dot == 0 {
			diff := len(s) - start
			if diff != 1 && s[start] == '0' {
				return
			}
			now := s[start:]

			now1, _ := strconv.Atoi(now)
			if now1 >= 0 && now1 <= 255 {
				ans = append(ans, prefix+now)
			}
			return
		}
	  // 如果发现以0开始，那么这个位置只能是0，不可以与其他的位组成数字。
		if s[start] == '0' {
			dfs(start+1, dot-1, prefix+"0.")
			return
		}

    // 123这种情况，我们可以分别尝试1，12，123这几种情况，然后再计算余下的字符串是否可以组成合法ip
		for end := start; end <= start+2 && end < len(s); end++ {
			now := s[start : end+1]
			now1, _ := strconv.Atoi(s[start : end+1])
			if now1 >= 0 && now1 <= 255 {
				dfs(end+1, dot-1, prefix+fmt.Sprintf("%s.", now))
			}
		}
	}

	dfs(0, 3, "")
	return ans
}