Short Encoding of Words
Medium · Trie · about 20 minutes
Asked at Google, Amazon, Meta.
An encoding of a word list is a reference string ending each encoded word with '#', plus indices, such that every word appears in the reference string starting at its index and ending just before a '#'. Return the length of the shortest possible reference string. (A word can share an encoding only with a word it is a suffix of.)