class Solution(object):
      def restoreIpAddresses(self, s):
          """
          :type s: str
          :rtype: List[str]
          """
          result = []
          ip = []
          self.dfs(s, ip, result, 0)
          return result

      def dfs(self, s, ip, result, start):
          # 满足条件的解的判断
          # 关键点是start==len(s)的判断

          if len(ip) == 4 and start == len(s):
              result.append(".".join(ip[:]))
              return
          # 剪枝条件判断
          if len(s)-start > (4-len(ip))*3:
              return
          if len(s)-start < 4-len(ip):
              return
          num = 0
          for i in range(start, min(start+3, len(s))):
              num = num*10+int(s[i])
              if num==13:
                  print("num")
              if num < 0 or num > 255: continue
              ip.append(s[start:i+1])
              self.dfs(s,ip, result, i+1)
              ip.pop(-1)
              if (num == 0): break






  print(Solution().restoreIpAddresses("25525511135"))