Longest Common Prefix

1. Define the problem

Given a list of words, find the longest common prefix shared by every single one of them. If there is no shared start, return the empty string "" . Put every word into a trie. Because words that start the same share the same path, the answer is simply how far you can walk down from the root before the path splits. You stop walking as soon as a node has more than one child letter (the words disagree from here on) or a node is the end of a word (one word has run out, so nothing longer can be common).

Constraints

1 ≤ strs.length ≤ 200
0 ≤ strs_i.length ≤ 200
strs_i consists of lowercase English letters only

Example

Inputstrs = ["flower", "flow", "flight"]

Output"fl"

Explanation All three words start with "f", then all three continue with "l". At the next letter they split into "o" and "i", so the walk stops and the answer is "fl".

2. Know the words first

In plain terms

Common prefix: A beginning that every word shares. For "flower", "flow" and "flight" the common prefix is "fl".
Branching node: A node in the trie with two or more different next letters. It is the point where the words stop agreeing.
Empty string: A string with no characters, written "". It is the answer when the words share nothing at all.

3. Visualize the solution

Walking down the trie until the words disagree

f—

l—

o—

w—

e—

r—

Statusinit

All three words are inserted into the trie, then the walk starts at the root.

What happens in this step

strs = ["flower", "flow", "flight"]
prefix = ''
node = root

The root itself holds nothing; the answer is built by stepping down from it.

Step 1 of 5

Steps to visualize

The row of cells is the path being walked down the trie, one cell per letter of the longest word.
The value shows what the node at that depth looks like: how many different next letters it offers.
"one" means every word agrees here, so the letter joins the answer.
"split" means the node has two or more next letters, so the walk stops immediately.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walking down the trie until the words disagree

f—

l—

o—

w—

e—

r—

Statusinit

All three words are inserted into the trie, then the walk starts at the root.

What happens in this step

strs = ["flower", "flow", "flight"]
prefix = ''
node = root

The root itself holds nothing; the answer is built by stepping down from it.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function longestCommonPrefix(strs) {
  if (strs.length === 0) {
    return '';
  }

  class TrieNode {
    constructor() {
      this.children = {};
      this.isEnd = false;
    }
  }

  const root = new TrieNode();

  for (const word of strs) {
    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  let prefix = '';
  let node = root;

  while (true) {
    const keys = Object.keys(node.children);
    if (keys.length !== 1 || node.isEnd) {
      break;
    }
    prefix += keys[0];
    node = node.children[keys[0]];
  }

  return prefix;
}

Time: O(total letters across all words)
Space: O(total letters across all words)

6. Test cases

Test cases

Input	Expected	Covers
`strs = ["flower", "flow", "flight"]`	`"fl"`	example from the docstring
`strs = ["dog", "racecar", "car"]`	`""`	the words share no starting letter at all
`strs = ["alone"]`	`"alone"`	one word is its own longest common prefix
`strs = ["", "abc"]`	`""`	an empty word forces the answer to be empty
`strs = ["ab", "abab", "abc"]`	`"ab"`	the shortest word is itself the common prefix
`strs = ["interspecies", "interstellar", "interstate"]`	`"inters"`	a long shared start across longer words

Longest Common Prefix