Longest Common Prefix

The problem, simply

You get a list of n words. Find the longest piece that all of them start with. That piece is called the common prefix. If they do not even share a first letter, give back an empty string "".

Below, m is the length of the shortest word. The answer can never be longer than that.

A story to remember it

Picture it

Examples

Way 1: the simple way

Guess the answer's length. Start with the longest possible guess, the length of the shortest word. Check if every word starts with that many letters of the first word. If not, try one letter shorter.

1. Find m, the length of the shortest word.
2. For len = m down to 0, take guess = first word, cut to len letters.
3. If every word starts with guess, return it.

class Solution {
    public String longestCommonPrefix(String[] words) {
        if (words.length == 0) return "";
        int m = Integer.MAX_VALUE;
        for (String w : words) m = Math.min(m, w.length());
        for (int len = m; len >= 0; len--) {
            String guess = words[0].substring(0, len);
            boolean everyone = true;
            for (String w : words) {
                if (!w.startsWith(guess)) { everyone = false; break; }
            }
            if (everyone) return guess;       // longest guess that works
        }
        return "";
    }
}

How long it takes: up to m + 1 guesses, and each one checks n words of up to m letters, so O(n * m^2). Extra room: the guess string, O(m).

Way 2: the clever way

Do the class chant. Read column 0 of every word, then column 1, and so on. Stop at the first column where a word disagrees or runs out. Nothing is checked twice.

1. For each column c of the first word, take the letter ch = words[0][c].
2. For every other word: if it is too short or its letter at c is not ch, stop and return the first c letters.
3. If the loop finishes, the whole first word is the answer.

class Solution {
    public String longestCommonPrefix(String[] words) {
        if (words.length == 0) return "";
        String first = words[0];
        for (int c = 0; c < first.length(); c++) {
            char ch = first.charAt(c);
            for (int k = 1; k < words.length; k++) {
                // this word ran out, or says a different letter
                if (c >= words[k].length() || words[k].charAt(c) != ch) {
                    return first.substring(0, c);
                }
            }
        }
        return first;                         // everyone matched the whole first word
    }
}

How long it takes: we read at most m + 1 columns of n words, so O(n * m). That is never more than the total number of letters. Extra room: a few counters, O(1), not counting the answer.

Way 3: sort, then compare two words

Sort the words in dictionary order. The first and the last word are the two most different ones. Whatever they share, every word in between shares too. So compare only those two.

import java.util.*;

class Solution {
    public String longestCommonPrefix(String[] words) {
        if (words.length == 0) return "";
        String[] w = words.clone();
        Arrays.sort(w);
        String a = w[0], b = w[w.length - 1];
        int i = 0;
        while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;
        return a.substring(0, i);
    }
}

This is short to write, but sorting costs O(n log n) comparisons of up to m letters each, so O(n * m log n). Good to mention, but Way 2 is faster.

Watch out for

• An empty list has no prefix. Return "" first.
• One word is its own answer. Way 2 handles it because the inner loop does nothing.
• indexOf(prefix) == 0 works but searches the whole word. startsWith is the right check.
• Do not sort the caller's array in place unless you are allowed to. Way 3 clones it.

What interviewers ask next

• Many questions about the same word list? Put all words in a letter tree (a trie). Walk down from the top while there is only one branch and no word ends. That path is the prefix.
• Can you split the work? Yes. The prefix of the left half and the prefix of the right half, then the prefix of those two. That is divide and conquer, still O(n * m).
• Binary search on the length? Check if the first mid letters are shared. That gives O(n * m log m), worse here, but it shows you can binary search on an answer.
• Longest common suffix? Do the same from the right end of every word.

Remember this

Grown-up words: the chant is vertical scanning, the shared start is the longest common prefix, the letter tree is a trie, and splitting the list in halves is divide and conquer.