[LeetCode] 93. Restore IP Addresses

Problem : https://leetcode.com/problems/restore-ip-addresses/

Use backtracking approach. For every digit, it can be either used as a new segment or used to extend the last segment.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        
        def backtracking(i, partial):
            if i == len(s):
                if len(partial) == 4:
                    ip = ".".join(partial)
                    result.append(ip)
                return
            
            # append new segment
            if len(partial) < 4:
                partial.append(s[i])
                backtracking(i+1, partial)
                partial.pop()
         
            # extend last segment
            if partial and partial[-1] != '0' and int(partial[-1] + s[i]) <= 255:
                partial[-1] = partial[-1] + s[i]
                backtracking(i+1, partial)
                partial[-1] = partial[-1][:-1]

        
        backtracking(0, [])
        
        return result