Simple, Intiutive Python Recursive Solution


  • 0
    D

    `
    class Solution(object):

    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        
        answer = []
        
        def helper(s, compRem):
            answer = []
            
            sLen = len(s)
            
            if compRem == 1:
                if sLen == 1:
                    answer.append(s)
                elif sLen == 2 and s[0] != '0':
                    answer.append(s)
                elif sLen == 3 and s[0] != '0' and int(s) < 256:
                    answer.append(s)
                
                return answer
            
            if (sLen < compRem) or ((3 * compRem) < sLen):
                return answer
            
            if sLen == compRem:
                answer.append('.'.join(s))
                return answer
            
            if s[0] == '0':
                deep = helper(s[1:], compRem - 1)
                for d in deep:
                    answer.append('0.' + d)
                return answer
            
            deep = helper(s[1:], compRem - 1)
            for d in deep:
                answer.append(s[0] + '.' + d)
            
            if sLen > 1:
                deep = helper(s[2:], compRem - 1)
                for d in deep:
                    answer.append(s[:2] + '.' + d)
            
            if sLen > 2 and int(s[:3]) < 256:
                deep = helper(s[3:], compRem - 1)
                for d in deep:
                    answer.append(s[:3] + '.' + d)
                
            return answer
        
        return helper(s, 4)
    

    `


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.