A straight forward Python solution using backtracking


  • 0
    C

    This code is quite straight forward, it should explain itself with the help of comments, although it's not very fast :(

     def generateAbbreviations(word):
                #Replace characters with '*', collect all the permutations of replacements
                def permutations(word, mp):
                    ret = []
                    if not word:
                        return [""]
                    if not mp.has_key(word):
                        nxt = permutations(word[1:], mp)
                        for item in nxt:
                            ret += ['*' + item, word[0] + item]
                        mp[word] = ret    
                    return mp[word]
                    
                    
                #Turn all the '*' into numbers, ie, '*'->'1', '**'->'2', '***'->3 
                def replace(s):
                    i = j = 0
                    ret = ''
                    while j <= len(s):
                        if j == len(s) or s[j] != '*':
                            if j > i:
                                ret += '%d' % (j - i)
                            i = j + 1
                            if j != len(s):
                                ret += s[j] 
                        j += 1
                    return ret
                    
                return map(replace, permutations(word, {}))

Log in to reply
 

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