10 lines beat 99.54% Python

  • 0
        def generateAbbreviations(self, word):  
            def abbreviate(s, w_chars): 
                if not s:
                    return "1" 
                if s[-1] in w_chars:
                    return s + "1" 
                    return s[:-1] + str(int(s[-1]) + 1)
            w_set = set(word)
            tree = [""]
            for l in word:
                tree = [ abbreviate(s,w_set) for s in tree] + [s+l for s in tree]
            return tree
    The idea is to construct a binary tree starting with the root which contains an empty string. As we stop down a level the one of the child will abbreviate the next letter and the other one will be concatenated with the next letter. 
    In the above code, the 'tree' variable is the root at the beginning but it keeps track of the bottom-most layer of the tree , which at the end will contain all 2^n subsets.

Log in to reply

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