Simple and intuitive Python solution, memoization


  • 0

    Code should be self-explanatory.

    class Solution(object):
        def generateAbbreviations(self, word):
            def generate(word, memo={"":{""}}):
                if word in memo: return memo[word]
                ret_set = set()
                for i in range(len(word)):
                    for abbr in generate(word[i + 1:], memo):
                        string = word[:i + 1] + abbr
                        ret_set.add(string)
                        if not abbr or abbr[0] not in "0123456789":
                            ret_set.add(str(i + 1) + abbr)
                memo[word] = ret_set
                return ret_set
                        
            return list(generate(word))
            
            # 49 / 49 test cases passed.
    	# Status: Accepted
            # Runtime: 528 ms
    

Log in to reply
 

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