Short Encoding of Words (LeetCode 820)

The problem

You want to encode a list of words as one string where each word is followed by #, and every word can be read off as a substring that ends just before some #. Words that are suffixes of other words can reuse them. Return the length of the shortest such string.

Input:  ["time", "me", "bell"]
Output: 10

The string "time#bell#" works: time starts at 0, me starts at 2 (the tail of time), and bell starts at 5. Its length is 10.

How to think about it

Start with brute force. Put the words in a set. For each word, remove every proper suffix of it from the set, because those can hide inside it. Whatever remains must be written out, each costing len + 1. That costs O(L²) per word for the suffix slices, which is fine here, but it hides the structure.

The key insight: a word can be hidden only if it is a suffix of another word. The encoding only lets you read a word that ends at a #, so me can hide in time but ti cannot. Suffix questions are awkward for a trie, which shares prefixes. So reverse every word: time becomes emit and me becomes em. Now “is a suffix of” turns into “is a prefix of”, and the reversed me lies on the path of the reversed time.

Only leaves cost anything. After inserting all reversed words, a word whose end node still has children is a prefix of a longer reversed word, which means it is hidden inside it for free. A word whose end node is a leaf (no children) is not covered by anything and must be written out, costing len(w) + 1 for the #.

Which pattern is this? A trie on reversed strings. The tell is “suffix” in a problem about sharing parts of words. Deduplicate first so a repeated word is not counted twice.

Approach

1. Deduplicate the words with set.
2. Insert each word reversed into a trie, and remember the end node together with len(w) + 1.
3. After all insertions, look at each remembered end node.
4. Add len(w) + 1 for every end node that is empty (a leaf). Skip the rest.

Solution

def minimum_length_encoding(words):
    root = {}; leaves = []
    for w in set(words):                               # drop duplicates
        node = root
        for ch in reversed(w): node = node.setdefault(ch, {})   # suffix -> prefix
        leaves.append((node, len(w) + 1))
    return sum(length for node, length in leaves if not node)    # only leaves cost
# minimum_length_encoding(["time", "me", "bell"]) -> 10   ("time#bell#")

Checking if not node after all insertions matters: me might be inserted before time, and its node only gains a child later.

Dry run

Reversed words are emit, em, lleb. After inserting all three:

Total: 5 + 5 = 10.

Complexity

• Time: O(S), where S is the total number of characters. Each character is inserted once, and the final sum is one pass over the words.
• Space: O(S) for the trie.

Edge cases and pitfalls

• Duplicates (["time", "time"]): without set, both copies end at the same leaf and you count 10 instead of 5.
• One word costs len + 1, for example ["t"] gives 2.
• Several words sharing a suffix (["time", "atime", "btime"]): time is hidden, the other two are leaves, total 12.
• Prefix trie instead of reversed is the common mistake. A prefix of a word cannot be read off before a #.

Related problems

• Implement Trie (Prefix Tree) (LeetCode 208): the trie insert used here.
• Replace Words (LeetCode 648): the prefix version of “does one word sit inside another”.
• Longest Common Prefix (LeetCode 14): reading structure from where a trie branches and ends.