题目
代码与解析
这道题和 二叉树所有路径以及https://blog.devilwst.top/2021/12/30/很像。
差不多是https://blog.devilwst.top/2021/12/30/这道题的兄弟。
大致核心是收集所有路径,把符合条件的节点添加到path.和分割回文串一样,这个也是分割问题!!!!
回溯三部曲:
- 确定递归参数及返回值
只需要传入start用于记录索引。 -
确定终止条件
这个终止条件和https://blog.devilwst.top/2021/12/30/这个不一样,
很容易忽略start的位置。start==len(s)
这个容易忽略
len(path)==4&&start==len(s)
if len(path)==4&&start==len(s){
temp := strings.Join(path, ".")
res = append(res, temp)
return
}
- 确定单层逻辑
和上一道差不多。大差不差。符合条件的就添加进path
for i:=start;i<len(s);i++{
subString := s[start: i+1]
if isValid(subString){
path = append(path, subString)
}else{
continue
}
backtracking(i+1)
path = path[:len(path)-1]
}
- IP有效验证
我写的比较乱
注意s[startIndex]=='0'的判断,不应该写s[startIndex]==0,因为s截取出来不是数字
func isValid(str string)bool{
if len(str)==1{
return true
}
// 到下面说明当前段 长度大于1
start := str[0] - '0'
// 长度大于1,第一位还等于0,false
if start==0{
return false
}
// 转换为int判断是否小于255
s, _ := strconv.ParseInt(str, 10, 32)
if s>255{
return false
}
return true
}
---------------------下面是一位大佬的代码-------------------------
func isIp3(s string,startIndex,end int)bool{
checkInt,_:=strconv.Atoi(s[startIndex:end+1])
if end-startIndex+1>1&&s[startIndex]=='0'{//对于前导 0的IP(特别注意s[startIndex]=='0'的判断,不应该写成s[startIndex]==0,因为s截取出来不是数字)
return false
}
if checkInt>255{
return false
}
return true
}
————选自carl大佬博客https://programmercarl.com/0093.复原IP地址.html#go 片段
整体代码:
func restoreIpAddresses(s string) []string {
res := []string{}
path := []string{}
var backtracking func(start int)
backtracking = func(start int){
if len(path)==4&&start==len(s){
// temp := strings.Join(path, ".")
temp:=""
for i:=0;i<=2;i++{
temp = temp + path[i] + "."
}
temp += path[3]
res = append(res, temp)
return
}
for i:=start;i<len(s);i++{
subString := s[start: i+1]
if isValid(subString){
path = append(path, subString)
}else{
continue
}
backtracking(i+1)
path = path[:len(path)-1]
}
}
backtracking(0)
return res
}
func isValid(str string)bool{
if len(str)==1{
return true
}
// 到下面说明当前段 长度大于1
start := str[0] - '0'
// 长度大于1,第一位还等于0,false
if start==0{
return false
}
// 转换为int判断是否小于255
s, _ := strconv.ParseInt(str, 10, 32)
if s>255{
return false
}
return true
}