题目

leetcode:93

代码与解析

这道题和 二叉树所有路径以及http://blog.devilwst.top/2021/12/30/很像。
差不多是http://blog.devilwst.top/2021/12/30/这道题的兄弟。

大致核心是收集所有路径，把符合条件的节点添加到path.和分割回文串一样，这个也是分割问题！！！！

回溯三部曲：

• 确定递归参数及返回值
  只需要传入start用于记录索引。

• 确定终止条件
  这个终止条件和http://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
}