Longest common prefix

Lesson 13.5 · Easy · Single-branch walk · 6 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Find the longest prefix shared by all the words.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

r10

Longest common prefix of 5 words. Walk down from the root while there is only one branch.

words [transformer, transformers, transformation, transforming, transformed]

1 / 11

The idea

Complexity

Time	Space	Why
`O(total letters)`	`O(total letters)`	Build the trie, then walk while each node has one child.

In Python

def longest_common_prefix(words):
    root = {}
    for w in words:
        node = root
        for ch in w: node = node.setdefault(ch, {})
        node['$'] = True
    out, node = [], root
    while len(node) == 1 and '$' not in node:
        ch = next(iter(node)); out.append(ch); node = node[ch]
    return ''.join(out)

Try it on LeetCode: Longest Common Prefix →

Summary: say it in the interview

Put all words in a trie. The common prefix is the path from the root while every node has exactly one child and no word ends. The first node with two branches, or a word end, is where the words disagree.
Time O(total letters), space O(total letters). Build the trie, then walk while each node has one child.