def generateAbbreviations(self, word): def abbreviate(s, w_chars): if not s: return "1" if s[-1] in w_chars: return s + "1" else: 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.
10 lines beat 99.54% Python
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.