Longest Common Prefix (LeetCode 14)

The problem

You get a list of strings. Return the longest string that is a prefix of every one of them. If they share nothing at the start, return the empty string "".

Input:  ["flower", "flow", "flight"]
Output: "fl"

All three start with fl, but at the third character they split into o and i, so the common prefix stops there.

How to think about it

Start with brute force. Take the first string and try every prefix of it, longest first, checking whether each other string starts with it. With n strings of length up to m, that is up to m candidate prefixes times n·m work each, so O(n·m²). It works, but it repeats the same character comparisons again and again.

The key insight: a common prefix is a path with no branching. Put every word into a trie. Words that agree on their first k characters share the same first k nodes. The moment two words disagree, the trie branches. The moment a word ends, there is an end marker. So the longest common prefix is exactly the path from the root that you can follow while each node has one child and no word ends there.

Why the end marker matters. For ["ab", "a"], the node after a has one child (b), but the word "a" ends there. The prefix cannot be longer than the shortest word, so you must stop at an end marker too.

Which pattern is this? Trie, prefix walk. The tell is “prefix shared across a set of words”. A simpler vertical scan (compare column by column) also solves this in O(1) extra space, but the trie version generalises to harder prefix questions.

Approach

1. Build a trie as a dict of dicts. For every word, walk or create one node per character and put "$" in the last node to mark a word end.
2. Start at the root with an empty prefix.
3. While the current node has exactly one key and that key is not "$", append that character to prefix and step into it.
4. Stop when the node branches, is empty, or marks a word end. Return prefix joined into a string.

Solution

def longest_common_prefix(strs):
    root = {}
    for w in strs:
        node = root
        for ch in w: node = node.setdefault(ch, {})
        node["$"] = True                       # a word ends here
    prefix, node = [], root
    while len(node) == 1 and "$" not in node:  # single branch, no word ends
        ch = next(iter(node)); prefix.append(ch); node = node[ch]
    return "".join(prefix)
# longest_common_prefix(["flower", "flow", "flight"]) -> "fl"
# longest_common_prefix(["dog", "racecar", "car"]) -> ""

Dry run

On ["flower", "flow", "flight"], after building the trie, the walk sees:

The walk stops at the branch, so the answer is "fl".

Complexity

• Time: O(S), where S is the total number of characters across all strings. Each character is inserted once, and the walk is at most as long as the shortest word.
• Space: O(S). In the worst case (no shared prefixes) the trie has one node per character. Vertical scanning avoids this and uses O(1) extra space.

Edge cases and pitfalls

• Empty list gives an empty root, so the loop never runs and you get "".
• An empty string in the list puts "$" on the root, so the answer is "" straight away.
• One word is a prefix of another (["ab", "a"]): the end marker stops the walk at "a". Forgetting the "$" check returns "ab", which is wrong.
• Duplicates (["a", "a"]) are fine: they share a path and mark the same end.
• No overlap at all (["dog", "racecar", "car"]): the root already has three children, so the answer is "".

Related problems

• Implement Trie (Prefix Tree) (LeetCode 208): the dict-of-dicts trie this solution builds on.
• Replace Words (LeetCode 648): walk a trie to find the shortest stored prefix of each word.
• Longest Happy Prefix (LeetCode 1392): a different prefix question, solved with string matching.