Python dynamic programming solution


  • 0
    A
    class Solution(object):
        def generateAbbreviations(self, word):
            dp = {}
            dp [''] = ['']
            return self.gar(word, dp)
    
        def gar(self, word, dp):
            if word not in dp:
                allres = [word]
                for p in xrange(len(word)):
                    for l in xrange(1, len(word)+1-p):
                        res = self.gar(word[p+l+1:], dp)
                        pre = word[:p] +str(l) + word[p+l:p+l+1]
                        res = [pre + x for x in res]
                        allres.extend(res)
                dp[word] = allres
            return dp[word]
    

Log in to reply
 

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