Restore IP Address

题目描述

解题方法

这种要求所有解的一般都是dfs+backtracking

现在的选择

• 前三位数可以选择

选择的限制

• 要小于255
• 不能有连续的0

结束条件

• 完成了4个部分
• 并且string都用完了

Solution

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

        return result

    def dfs(self, s, result, part, cur_str):
        if part == 4:
            if s == "": # 应该放在下面，这样part==4就退出了
                result.append(cur_str[1:])
            return
        else:
            for i in range(1, 4): # try first 3 chars
                if i <= len(s):
                    if int(s[:i]) <= 255:
                        self.dfs(s[i:], result, part+1, cur_str+"."+s[:i])
                    else:
                        break
                    if s[0] == "0": # 0 can only be 0
                        break

Reference