Description:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Solution:
NOTE: 注意用“str(int(s)) == s”去开头的0,eg. "010" 不能被当做 "10"
NOTE: string[0] != "0"不能去开头的0,因为0本身是符合的,但不满足这个条件
class Solution:
def restoreIpAddresses(self, s: str,num = 4) -> List[str]:
if len(s) < num or len(s) > num*3:
return []
if num == 1 and int(s) < 256 and str(int(s)) == s: # 只剩一个slot了
return [s]
ls = [s[:1],s[:2],s[:3]]
result = []
for i in range(3):
head = ls[i]
if int(head) > 255 or str(int(head)) != head: # 数字太大 或者 开头有0
break
if i+1 < len(s):
for r in self.restoreIpAddresses(s[i+1:],num-1):
result.append(head+"."+r)
return result
Runtime: 36 ms, faster than 91.37% of Python3 online submissions for Restore IP Addresses.
Memory Usage: 13.3 MB, less than 25.00% of Python3 online submissions for Restore IP Addresses.