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"))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61899.html
標籤：Python
上一篇：99恢復二叉樹
下一篇：06自動登錄淘寶