93_复原_IP_地址

类型：字符串

• 93. 复原 IP 地址 💛

  https://leetcode-cn.com/problems/restore-ip-addresses/

  ❓ 有一个表示 IP 地址的字符串，但是用于分割的小数点被抹掉了。我们向其中添加小数点，可以构成几种有效的 IP 地址？

  💡 回溯

  class Solution:
      def restoreIpAddresses(self, s: str) -> List[str]:
          SEG_COUNT = 4
          ans = list()
          segments = [0] * SEG_COUNT
  
          def dfs(segId: int, segStart: int):
              # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
              if segId == SEG_COUNT:
                  if segStart == len(s):
                      ipAddr = ".".join(str(seg) for seg in segments)
                      ans.append(ipAddr)
                  return
  
              # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
              if segStart == len(s):
                  return
  
              # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
              if s[segStart] == "0":
                  segments[segId] = 0
                  dfs(segId + 1, segStart + 1)
  
              # 一般情况，枚举每一种可能性并递归
              addr = 0
              for segEnd in range(segStart, len(s)):
                  addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                  if 0 < addr <= 0xFF:
                      segments[segId] = addr
                      dfs(segId + 1, segEnd + 1)
                  else:
                      break
  
  
          dfs(0, 0)
          return ans