描述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

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

Python

笨方法

class Solution:
    def restoreIpAddresses(self, s):
        ret = []
        for a in range(1, 4):
            for b in range(1, 4):
                for c in range(1, 4):
                    d = len(s) - a - b - c
                    """
                      Last number must use all remaining digits. Check;
                      1. The size of the last number is valid
                      2. Every number uses 1 digit for 0 and is less than 255 if using 3 digits
                    """
                    if (1 <= d <= 3 and
                    (1 == a or '0' != s[0        ]) and (a != 3 or s[         :a        ] <= "255") and
                    (1 == b or '0' != s[a        ]) and (b != 3 or s[a        :a + b    ] <= "255") and
                    (1 == c or '0' != s[a + b    ]) and (c != 3 or s[a + b    :a + b + c] <= "255") and
                    (1 == d or '0' != s[a + b + c]) and (d != 3 or s[a + b + c:         ] <= "255")):
                        ret.append('.'.join([s[0:a], s[a:a + b], s[a + b:a + b + c], s[a + b + c:]]))
        return ret

backtracking(更好的方案)

class Solution:
    def restoreIpAddresses(self, s):
        ret = []
        self.dfs(s,0,'',ret)
        return ret
    
    def dfs(self,s,index,path,ret):
        if index == 4:# already have 4 items
            if not s: 
                ret.append(path[:-1]) # leave the last '.'
            return # attention backtracking needs return when is working or not
    
        for i in range(1,4):# 3 is the max length
            if i <=len(s):
                if i==1 :
                    self.dfs(s[i:],index+1,path+s[:i]+'.',ret)
                if i==2 and s[0] != '0':
                    self.dfs(s[i:],index+1,path+s[:i]+'.',ret)
                if i==3 and s[0] != '0' and int(s[:i])<=255:
                    self.dfs(s[i:],index+1,path+s[:i]+'.',ret)