Shortest Encoding of a Word List
Problem
A list of lowercase words is stored as one reference string in which every word ends with a #, and each word is read by starting at some index and stopping at the next #. A word that is a suffix of another word therefore needs no space of its own: me can be read inside time#. Return the length of the shortest reference string that can encode all the words.
Examples
Input: words = ["time", "me", "bell"]
Output: 10
Why: time#bell# holds all three, with me read from index 2Input: words = ["atom", "tom", "m", "bat"]
Output: 9
Why: atom#bat#, since tom and m are both suffixes of atomInput: words = ["me", "me"]
Output: 3
Why: edge case, a repeated word is encoded onceHints
0 / 3
A word costs nothing exactly when it is a suffix of some other word. Every other word costs its length plus one for the #.
A hash set works: put in all words, remove every proper suffix of every word, and sum what is left. But producing every suffix copies letters, O(L²) per word of length L.
Suffixes become prefixes when words are reversed. Insert each distinct reversed word into a trie. A word is a suffix of another exactly when its last node has children, so only words ending at a leaf are paid for.
Solution
Reversing the words turns shared suffixes into shared prefixes, which is what a trie stores for free. After inserting each distinct reversed word, a word whose final node has children is the reversed prefix of a longer word, so it is a suffix of that word and rides inside its encoding. A word whose final node is a leaf must be written out with its #. Two different words cannot end at the same node, since the path spells the word, so counting leaves never double counts. The hash set version gives the same answer with less code but slices out every suffix of every word, which costs O(L²) per word; the trie touches each letter once. Time and space are O(W) for W total letters.
def encoding_length(words):
root, ends = {}, []
for w in set(words): # a repeated word is encoded once
node = root
for ch in reversed(w): # shared suffixes become shared prefixes
node = node.setdefault(ch, {})
ends.append((node, len(w)))
return sum(n + 1 for node, n in ends if not node) # only leaves need their own #
print(encoding_length(["time", "me", "bell"])) # -> 10
print(encoding_length(["atom", "tom", "m", "bat"])) # -> 9
print(encoding_length(["me", "me"])) # -> 3Stuck on the idea rather than the code? Trie vs Hash Set covers it.