- 分类:BackTracking
- 时间复杂度: O(1)
93. Restore IP Addresses
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"]
代码:
class Solution:
def restoreIpAddresses(self, s: 'str') -> 'List[str]':
res=[]
if s==None or len(s)<4:
return res
self.helper(res,s,[],4)
return res
def helper(self,res,s,my_ans,current):
if len(my_ans)==4 and s=="":
res.append(".".join(my_ans))
return
if s=="":
return
for i in range(current):
if len(s)>=3 and int(s[:3])>=100 and int(s[:3])<=255:
my_ans.append(s[:3])
self.helper(res,s[3:],my_ans,current-i-1)
my_ans.pop()
if len(s)>=2 and int(s[:2])>=10 and int(s[:2])<=99:
my_ans.append(s[:2])
self.helper(res,s[2:],my_ans,current-i-1)
my_ans.pop()
if len(s)>=1 and int(s[:1])>=0 and int(s[:1])<=9:
my_ans.append(s[:1])
self.helper(res,s[1:],my_ans,current-i-1)
my_ans.pop()
讨论:
1.可喜可贺,我自己可以完全不看解答把这个题做出来了