93. Restore IP Addresses - cocoder39/coco39_LC GitHub Wiki

93. Restore IP Addresses

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        self.helper(s, 0, [], res)
        return res
    
    def helper(self, s, start, path, res):
        if len(path) > 4:
            return
        
        if start == len(s):
            if len(path) == 4:
                res.append(".".join(path))
            return
        
        for i in range(start, min(start+4, len(s))):
            val = s[start:i+1]
            if int(val) > 255 or (i > start and s[start] == '0'):
                break
            path.append(val)
            self.helper(s, i+1, path, res)
            path.pop()