93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.'分隔。

示例:

输入: “25525511135”
输出: ["255.255.11.135", "255.255.111.35"]

代码：

  1. class Solution:
  2.     def restoreIpAddresses(self, s: str) -> List[str]:
  3.         self.res=[]
  5.         def backtrack(s, tmp):
  6.             if len(s) == 0 and len(tmp) == 4:
  7.                 self.res.append('.'.join(tmp))  # 用.分割合并的四个数字字符串
  8.                 return 
  9.             if len(tmp) < 4:
  10.                 for i in range(min(3, len(s))):
  11.                     now, left = s[:i+1], s[i+1:]
  13.                     # str(int(now)) == now是屏蔽0开头的数字字符串
  14.                     if now and 0<=int(now)<=255 and str(int(now)) == now:
  15.                         backtrack(left, tmp+[now])
  17.         backtrack(s, [])
  18.         return self.res