93复原IP地址。

from typing import List
# 这道题不是很难，但是限制条件有很多。
# 用递归的方法可以很容易的想到。只需要四层递归就好了。
# 每次进行加上限制条件。过滤每一层就好了。、
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        self.IP_lists = []
        self.dfs(s, "", 0)
        return self.IP_lists
# 定义递归函数，参数为字符串，IP字符串，还有递归层数
    def dfs(self, s, ip_str, depth):
        # 前三层。
        if depth < 3:
            # 最多可以取三个字符
            for index in range(1, 4):
                # 写限制条件，根据IP地址的规范
                if s != "" and 0 <= int(s[:index]) <= 255:
                    if int(s[:index]) == 0 and  len(s[:index]) != 1:
                        continue
                    elif int(s[:index]) != 0 and s[0] =="0":
                        continue
                        # ip_str = ip_str + s[:index] + '.'
                    else:
                        # 再次进行递归
                        self.dfs(s[index:], ip_str + s[:index] + '.', depth + 1)
        else:
            # 当来到第四层，剩下的s就是最后一数字
            # 判断最后一个数字是否符合条件。
            if s != "" and 0 <= int(s) <= 255:
                if int(s) == 0 and len(s) != 1:
                    pass
                elif  int(s) != 0 and s[0] == "0":
                    pass
                else:
                    ip_str = ip_str + s
                    self.IP_lists.append(ip_str)
A = Solution()
print(A.restoreIpAddresses("25525511135"))
print(A.restoreIpAddresses("2552"))
# print(A.restoreIpAddresses("000"))
print(A.restoreIpAddresses("010010"))
巴特西

93复原IP地址。

最新文章

热门文章
