Leetcode 93. Restore IP address

Problem no.93

Restore IP Address

 

Question:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

 

Solution:

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        l = len(s)
        if l < 4 or l > 4*3:
            return []
        
        ans = set()
        
        
        def recursive(ss, n, tmp):
            if len(ss) < n or len(ss) > n*3:
                return
            if n == 0 :
                if len(ss) == 0:
                    ans.add('.'.join(tmp))
                return 
            for i in range(1,4): #1~3
                if i > 1 and len(ss) > 1 and ss[0] == '0':
                    continue
                if i == 3 and len(ss) >=3 and int(ss[:3]) > 255:
                    continue
                
                recursive(ss[i:], n-1, tmp+[ss[:i]])
                
        recursive(s, 4, [])
        return ans

Result 

- Time complexity: top 80%

- Space complexity: top 50%. 

 

 

Backtracking

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

From geeksforgeeks

 

한 줄 정리

Choice  ↔ Constraint ↔ Goal