Longest common prefix in Python

Why this matters

A prefix is the start of a word or text. The prefix of interview of length 5 is inter. A common prefix is a start that several strings share. The longest common prefix of a set of strings is the longest start that all of them have.

Real programs need this. A file browser that autocompletes a path shows the longest shared start of the matching names. A router that groups URLs by their first segment finds a shared start in a list. A spell checker groups words that begin the same way. In each case the program receives a list of strings and must return one string, which is the shared start.

This lesson uses two methods for the same task. The first method starts with one string as a guess and cuts it shorter until every other string starts with that guess. The second method checks one column of characters at a time across all strings. Both methods are short, and each one teaches a habit that appears in later string problems. The lesson does not cover the Unicode issues from the code points lesson, and it does not cover searching for a pattern anywhere in a string, which is the subject of the naive substring search lesson.

The task in plain words

You get a list of words. You return the longest text that is the start of every word in the list.

These examples fix the rules before any code.

• ["flower", "flow", "flight"] returns "fl". All three start with fl. The fourth letter differs: o, o, i.
• ["dog", "racecar", "car"] returns "". The first letters differ, so the shared start is empty.
• ["interview"] returns "interview". A single word is its own shared start.
• ["same", "same", "same"] returns "same". Equal strings share everything.
• An empty list returns "". There are no strings to share, so the answer is the empty string.

The empty string "" is a real answer, not an error. A function that returns None for "nothing shared" makes the caller check for a special case. Returning "" lets the caller treat every answer the same way.

Method 1: cut the candidate down

Think of a line of text on a card. You hold up the first word. You check the second word. If the second word does not start with your card, you cut one letter off your card and check again. You keep cutting until the second word starts with what is left on your card. Then you check the third word against the card, and so on.

The card is the candidate, which means the current guess. Every cut makes the guess shorter, and every word that already matches keeps the guess valid. When the last word has been checked, the candidate is the answer.

In Python, the method str.startswith tells you whether a string begins with a given text. The slice prefix[:-1] removes the last character of the candidate. Here is the full function.

def by_shortening(words):
    if not words:
        return ""
    prefix = words[0]
    for word in words:
        while not word.startswith(prefix):
            prefix = prefix[:-1]
    return prefix

Read the two loops. The outer for loop visits each word. The inner while loop cuts the candidate until the current word starts with it. The if at the top handles the empty list, because words[0] would fail if the list had no items.

The while loop always stops. The empty string is the start of every string, because startswith("") is true for any word. So if the candidate is cut all the way to "", the loop ends there.

Following the cuts step by step

The function below is the same method with a print after each check and each cut. Run it on ["flower", "flow", "flight"].

The output is:

  after "flower": "flower"
  checking "flow": cut to "flowe"
  checking "flow": cut to "flow"
  after "flow": "flow"
  checking "flight": cut to "flo"
  checking "flight": cut to "fl"
  after "flight": "fl"
fl

The first word is the starting candidate, so it always matches itself. The word flow cuts the candidate twice, once to flowe and then to flow. The word flight cuts it twice more, to flo and then to fl. The answer is fl, which is the longest start that all three words share.

Notice that the candidate never grows. Once a cut has happened, the candidate stays short. This is why the method is correct: each cut removes text that some word does not have, so nothing that was cut could be part of the answer.

What this method costs

Each startswith check compares the candidate with the start of the word. The number of cuts is at most the length of the first word, because the candidate starts as the first word. In the worst case, the method checks every word many times. That is fine for short lists, but it does more work than it needs when the words differ early. Method 2 stops as soon as it sees a difference.

Method 2: compare column by column

Now look at the words in a grid. Put one word on each row, lined up at the left. Each vertical line of characters is a column. The column at index 0 holds the first letter of every word. The column at index 1 holds the second letter, and so on.

For ["flower", "flow", "flight"] the grid looks like this, with each column numbered.

column:  0 1 2 3 4 5
flower:  f l o w e r
flow:    f l o w
flight:  f l i g h t

Columns 0 and 1 hold f and l in every row. Column 2 holds o, o and i, so the words differ there. The shared start is the text in columns 0 and 1, which is fl.

The method walks the columns from left to right. For each column it checks every word. The first time a word is too short or has a different letter, the method returns the text up to that column. If every column matches, the method returns the first word.

def by_columns(words):
    if not words:
        return ""
    first = words[0]
    for col in range(len(first)):
        c = first[col]
        for word in words[1:]:
            if col >= len(word) or word[col] != c:
                return first[:col]
    return first

Two checks happen inside the inner loop. The first check, col >= len(word), catches a word that ends before this column. Without it, word[col] would read past the end of the word and fail. The second check, word[col] != c, compares the letter in this column with the letter in the first word. The check order matters: or stops at the first true part, so the length is tested before the letter is read.

The return first[:col] line returns the text before the mismatch. If the mismatch happens at column 0, first[:0] is the empty string, which is correct when the first letters differ.

Running the column method

Here are both functions on the same six lists. The program prints both answers for each list, so you can see that they agree.

The output is:

['flower', 'flow', 'flight'] -> shortening="fl" columns="fl"
['dog', 'racecar', 'car'] -> shortening="" columns=""
['interview'] -> shortening="interview" columns="interview"
['same', 'same', 'same'] -> shortening="same" columns="same"
['ab', 'a'] -> shortening="a" columns="a"
[] -> shortening="" columns=""

The list ["ab", "a"] shows the length check at work. Column 0 matches in both words. At column 1, the word a has no letter, so col >= len(word) is true and the function returns a.

Tracing the column method by hand

Before you run a function, you can trace it on paper. Write each column as one row of a table, then decide what the function does at that row. Here is the trace for ["flower", "flow", "flight"].

The table shows the rule in one place. A column continues only when every other word has the same letter there. The first column that fails ends the function, and the answer is everything before it.

Tracing on paper also shows the length check. Trace ["ab", "a"]. Column 0 holds a in both words, so it continues. Column 1 is past the end of the word a, so the check col >= len(word) is true and the function returns a. A trace that includes a short word is the fastest way to find a missing check.

A longer example

Take a list of five words that share the start inter.

The output is:

inter
inter
abcde

The last word, inter, is exactly five letters long. The column function stops when it reaches column 5 for that word, because col >= len(word) is true. The shortening function stops because the candidate has been cut to inter and every word starts with it.

The third case is a list where the words have a longer shared start and then differ near the end. The shared text is abcde. The sixth letter is f in one word and X in another, so the function stops at column 5.

Choosing between the two methods

Both methods give the same answers on every list in this lesson. They differ in how they work and in what they do when the words are long.

The column function creates one new string at the end. The shortening function creates a new string on every cut. For a few words this makes no difference. For thousands of long words, it can. In an interview, either method is correct if you explain it. In production code, the column method is usually a good default, because it stops at the first mismatch.

Edge cases

Edge cases are the inputs that the main idea does not seem to cover. The empty list has an explicit check at the top. The three cases below follow from the same rules, so run each one to check it.

The first edge case is an empty string in the list. An empty word has no letters, so no column can be shared with it. Here are both functions on two lists that contain "".

The output is:

["", "abc"] -> columns=[] shortening=[]
[abc, , abd] -> columns=[] shortening=[]

In the first list, the first word is the empty string, so both functions return it. In the second list, the empty word appears in the middle. The column function stops at column 0, because the word "" has length 0. The shortening function cuts the candidate abc down to "" when it reaches the empty word, and it then keeps "" for the rest of the list.

The second edge case is a list where a shorter word is itself the answer.

The output is:

columns=[ab] shortening=[ab]

Here the answer is the whole word ab, which is the shortest word in the list. The column function stops at column 2, because the word ab has no letter there. The shortening function cuts abc to ab, and then every word starts with ab.

The third edge case is a list with one word, which both functions return unchanged, as the example with ["interview"] showed. Together the three cases cover the rules: an empty word gives the empty answer, the shortest word can be the answer, and a single word is its own answer.

Common mistakes

Mistake 1: reading the first word without checking the list. An empty list has no first word, so words[0] fails.

The output is:

IndexError: list index out of range

The fix is the if not words: check at the top of both functions.

Mistake 2: relying on a slice to fail on a short word. A function that checks the start of a word by slicing it to the candidate's length does not raise an error when the word is shorter. The slice just returns less text, and the comparison fails, which makes the loop cut the candidate. The result is correct here, but the reason is easy to misread.

The output is:

fl 'fl' False
fl

Python never raises an error for a slice past the end, so the result is correct only by accident of the comparison. Use startswith, which says exactly what the check means, as the main function does.

Mistake 3: missing the length check in the column function. Without the col >= len(word) check, word[col] reads past the end of a short word.

The output is:

IndexError: string index out of range

The word a has length 1, so index 1 does not exist. The fix is the check that a word has the column before comparing letters. Unlike a slice, an index always raises an error when the position does not exist.

Mistake 4: comparing strings with is. Python's == compares the characters, so it is the right check. The mistake is to use is by habit. The is operator asks whether two names point to the same object, and that answer can change with how Python stores the strings. The example below compares the first letters of two words:

The output is:

True True
False False

The first line says True for is, but only because CPython keeps one shared object for each single-character string. The second line gives False for is, because the two-letter strings are separate objects. Both lines agree on ==, which is the right test. Use == to compare text, and use is only for None.

Mistake 5: returning None for no match. A function that returns None when there is no shared start forces the caller to check for None before printing or measuring the answer. Return "" instead. Every answer then has the same type, and len(result) is always safe to call.

Practice

Try each exercise before you read its answer. Run your code, so you can check the output.

1. Run by_columns on ["car", "cart", "carbon"]. What does it return, and at which column does it stop?

Show the answer

It returns car. Columns 0, 1 and 2 match in all three words. The outer loop ends after column 2, because the first word has only three letters, and the function returns first, which is car. No word is too short here, so the length check never fires.

2. Write a function two_strings(a, b) that returns the common prefix of exactly two strings, using a single loop with indexes.

Show the answer

def two_strings(a, b):
    n = min(len(a), len(b))
    i = 0
    while i < n and a[i] == b[i]:
        i += 1
    return a[:i]

Running it on "prefix" and "pre" gives pre. Running it on "abc" and "xyz" gives the empty string. Running it on "" and "a" gives the empty string.

3. Explain in your own words why the while loop in by_shortening always stops, even when no words share a start.

Show the answer

Every string starts with the empty string, so startswith("") is true for every word. When the candidate has been cut down to "", the check passes for every word and the loop ends. The function then returns "".

4. Mistake 3 fails on ["abc", "a"]. Add the length check to no_length_check so that it returns a for that input, and state which line you added.

Show the answer

Add col >= len(words[row]) or before the letter comparison. The line becomes if col >= len(words[row]) or words[row][col] != c:. The function then returns a for ["abc", "a"], because column 1 fails the length check for the word a.

5. Give one list where by_shortening makes more cuts than by_columns makes comparisons, and explain why. You do not need to count exactly.

Show the answer

Take ["abcdefgh", "xbcdefgh"]. The first letters differ. by_shortening cuts the candidate abcdefgh one letter at a time from the end, eight cuts in total, before it reaches "". by_columns checks column 0 for the second word, finds x instead of a, and returns after one comparison. The shortening method has to remove letters that the column method never looks at.

Summary

• The longest common prefix is the longest start that every string in a list shares. Return "" when nothing is shared.
• Method 1 keeps one candidate, cuts it from the end until each word starts with it, and never grows it.
• Method 2 compares the words one column at a time and returns at the first column where a word differs or ends.
• Check for an empty list before reading the first word, and check that a word is long enough before reading a column.
• Compare text with ==, never with is, and remember that a slice past the end never raises an error in Python.