93. Restore IP Addresses

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

Python

Backtracking

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        def backtracking(left, stack):
            if len(stack) == 4 and left == len(s):
                nonlocal ans
                ans.append('.'.join([str(num) for num in stack]))

            if len(stack) > 3:
                return

            if left < len(s) and s[left] == '0':
                stack.append('0')
                backtracking(left+1, stack)
                stack.pop()
                return

            for right in range(left+1, len(s)+1):
                cand = s[left:right]

                if int(cand) > 255:
                    continue
                stack.append(''.join(cand))
                backtracking(right, stack)
                stack.pop()

        backtracking(0, [])

        return ans