• 分類：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.可喜可賀，我自己可以完全不看解答把這個題做出來了