回溯算法 8. 复原IP地址

93. 复原 IP 地址 - 力扣（LeetCode）

代码随想录

难度 5 - 中等

• 其实就是要把s​分割成4个子串，然后看子串是否符合要求

  所以这也是一个分割问题，可以看成回溯算法 7. 分割回文串-CSDN博客的变式

• 要点：

  1. 检测子串s是否有效：

     下面是依次逐步检测，前次条件不符合才会跳转到后次条件（也就是if else嵌套）

     • 子串为单独的0，有效
     • 有前导0，无效
     • 剩下必无前导0，若子串在1~255之间，有效
     • 其他情况均无效

  2. 剪枝1：

     不符合[4,12]位长度的s，不管怎么分割都是无效ip

  3. 回溯设计：

     • 终止条件： 当path已经有4个元素

     • 循环+递归：

       ​for i in range(startIdx, len(s))​循环（横向拓展）：

       其中i​代表当前层的分割线放在索引为i​的元素的右侧，切出来的子串从startIdx​开始到分割线左侧为止；

       1. 剪枝2：

          当分割线放在索引为startIdx+3​元素的左侧时，分割线已经不能再往右侧放了，因为有效ip地址的任意子部分必须是0~255之间，不可能是4位及以上的数字

       2. 分割出新子串sub_s​，用end​记录分割线放置的位置（是分割线右侧第一个元素的索引）

          • 其中，剪枝3：

            当path​已经有3个元素时，当前从startIdx​开始的待处理子串应该整个作为新的结点

       3. 仅在当前分割出的子串sub_s​有效时继续拓展（纵向拓展，也就是递归）

       4. ​for​循环内部的最后处，进行前面的剪枝3：

          ​end​为len(s)​时，就说明当前层是path​已经有3个元素的情况，无需继续横向拓展了！直接break​即可

• 代码如下：

  class Solution:
      def restoreIpAddresses(self, s: str) -> List[str]:
          # 剪枝：不符合[4,12]位长度的s，不管怎么分割都是无效ip
          if len(s) < 4 or len(s) > 12:
              return []
  
          self.result = []
          self.path = []
          self.backTracking(s, 0)
          return self.result
  
      def backTracking(self, s, startIdx):
          # 其实就是要把s分割成4个子串，然后看子串是否符合要求
          # startIdx 是当前待处理子串的起始索引
  
          # 终止：当path已经有4个元素
          if len(self.path) == 4:
              self.result.append('.'.join(self.path))
              return
  
          for i in range(startIdx, len(s)):
              # i代表当前层的分割线放在索引为i的元素的右侧，切出来的子串从startIdx开始到分割线左侧为止
  
              # 剪枝：当分割线放在索引为startIdx+3元素的左侧时，分割线已经不能再往右侧放了，
              # 因为有效ip地址的任意子部分必须是0~255之间，不可能是4位及以上的数字
              if i - startIdx >= 3:
                  break
  
              # 分割出新子串sub_s
              if len(self.path) >= 3:
                  # 当path已经有3个元素时，当前从startIdx开始的待处理子串应该整个作为新的结点
                  end = len(s)          
              else:
                  end = i + 1
              sub_s = s[startIdx: end] # end为分割线右侧第一个元素的索引
  
              # 仅在当前分割出的子串有效时继续拓展
              if self.isValid(sub_s): 
                  self.path.append(sub_s)
                  self.backTracking(s, end)
                  self.path.pop() 
  
              # end为len(s)时，就说明是path已经有3个元素的情况，无需继续横向拓展了
              if end == len(s):
                  break
  
      def isValid(self, s):
          # 检测子串s是否有效
          if s == '0': # 子串为单独的0，有效
              return True
          elif s[0] == '0' and len(s) > 1: # 有前导0，无效
              return False  
          elif 1 <= int(s) <= 255: # 剩下必无前导0，若子串在1~255之间，有效
              return True
          else: # 其他情况均无效
              return False
  

• 可以参考该图理解整棵树的形状

• 时间复杂度: O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。

• 空间复杂度: O(n)

• 学习代码随想录知：

  也可以添加一个全局变量pointNum​，记录添加逗点的数量

  本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

  pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。

  然后验证一下第四段是否合法，如果合法就加入到结果集里

  感觉做法大差不差，就直接将各版本代码摘抄在下面了。

  • 版本一：

    class Solution:
        def restoreIpAddresses(self, s: str) -> List[str]:
            result = []
            self.backtracking(s, 0, 0, "", result)
            return result
    
        def backtracking(self, s, start_index, point_num, current, result):
            if point_num == 3:  # 逗点数量为3时，分隔结束
                if self.is_valid(s, start_index, len(s) - 1):  # 判断第四段子字符串是否合法
                    current += s[start_index:]  # 添加最后一段子字符串
                    result.append(current)
                return
    
            for i in range(start_index, len(s)):
                if self.is_valid(s, start_index, i):  # 判断 [start_index, i] 这个区间的子串是否合法
                    sub = s[start_index:i + 1]
                    self.backtracking(s, i + 1, point_num + 1, current + sub + '.', result)
                else:
                    break
    
        def is_valid(self, s, start, end):
            if start > end:
                return False
            if s[start] == '0' and start != end:  # 0开头的数字不合法
                return False
            num = 0
            for i in range(start, end + 1):
                if not s[i].isdigit():  # 遇到非数字字符不合法
                    return False
                num = num * 10 + int(s[i])
                if num > 255:  # 如果大于255了不合法
                    return False
            return True
    

  • 版本二：

    class Solution:
        def restoreIpAddresses(self, s: str) -> List[str]:
            results = []
            self.backtracking(s, 0, [], results)
            return results
    
        def backtracking(self, s, index, path, results):
            if index == len(s) and len(path) == 4:
                results.append('.'.join(path))
                return
    
            if len(path) > 4:  # 剪枝
                return
    
            for i in range(index, min(index + 3, len(s))):
                if self.is_valid(s, index, i):
                    sub = s[index:i+1]
                    path.append(sub)
                    self.backtracking(s, i+1, path, results)
                    path.pop()
    
        def is_valid(self, s, start, end):
            if start > end:
                return False
            if s[start] == '0' and start != end:  # 0开头的数字不合法
                return False
            num = int(s[start:end+1])
            return 0 <= num <= 255
    

  • 版本三：

    class Solution:
        def restoreIpAddresses(self, s: str) -> List[str]:
            result = []
            self.backtracking(s, 0, [], result)
            return result
    
        def backtracking(self, s, startIndex, path, result):
            if startIndex == len(s):
                result.append('.'.join(path[:]))
                return
    
            for i in range(startIndex, min(startIndex+3, len(s))):
                # 如果 i 往后遍历了，并且当前地址的第一个元素是 0 ，就直接退出
                if i > startIndex and s[startIndex] == '0':
                    break
                # 比如 s 长度为 5，当前遍历到 i = 3 这个元素
                # 因为还没有执行任何操作，所以此时剩下的元素数量就是 5 - 3 = 2 ，即包括当前的 i 本身
                # path 里面是当前包含的子串，所以有几个元素就表示储存了几个地址
                # 所以 (4 - len(path)) * 3 表示当前路径至多能存放的元素个数
                # 4 - len(path) 表示至少要存放的元素个数
                if (4 - len(path)) * 3 < len(s) - i or 4 - len(path) > len(s) - i:
                    break
                if i - startIndex == 2:
                    if not int(s[startIndex:i+1]) <= 255:
                        break
                path.append(s[startIndex:i+1])
                self.backtracking(s, i+1, path, result)
                path.pop()
    

‍