前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的93题。
问题描述
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例 1：
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
分析：
回溯法
func restoreIpAddresses(s string) []string {
temp := make([]int, 0)
ret := make([]string, 0)
dfs(s, 0, 1, &temp, &ret)
return ret
}
func dfs(s string, index, lay int, temp *[]int, ret *[]string) {
if lay == 4 {
if s[index] == '0' && len(s) - index != 1 {
return
}
i, _ := strconv.Atoi(s[index:])
if i < 256 {
var r string
for j := 0; j < 3; j++ {
r += strconv.Itoa((*temp)[j]) + "."
}
r += strconv.Itoa(i)
*ret = append(*ret, r)
}
return
}
if index + 1 >= len(s) {
return
}
i, _ := strconv.Atoi(s[index:index+1])
if len(s) - index - 1 <= (4 - lay) * 3 {
t := append(*temp, i)
dfs(s, index + 1, lay + 1, &t, ret)
}
if s[index] == '0' {
return
}
if index + 2 >= len(s) {
return
}
i, _ = strconv.Atoi(s[index:index+2])
if len(s) - index - 2 <= (4 - lay) * 3 {
t := append(*temp, i)
dfs(s, index + 2, lay + 1, &t, ret)
}
if index + 3 >= len(s) {
return
}
i, _ = strconv.Atoi(s[index:index+3])
if len(s) - index - 3 <= (4 - lay) * 3 && i < 256{
t := append(*temp, i)
dfs(s, index + 3, lay + 1, &t, ret)
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
