LC 0093 [M] Restore IP Addresses - ALawliet/algorithms GitHub Wiki

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        
        if len(s) > 12:
            return res
        
        def branch(i, dots, curIP):
            if dots == 4 and i == len(s):
                res.append(curIP[:-1]) # chop off last '.'
                return
            
            elif dots > 4: # invalid ip
                return
            
            else:
                for j in range(i, min(i + 3, len(s))):
                    noLeading0s = i == j or s[i] != '0'
                    if int(s[i:j+1]) < 256 and noLeading0s:
                        branch(j + 1, dots + 1, curIP + s[i:j+1] + '.')
                    
        branch(0, 0, '')
        return res