Longest Common Prefix

Q: What is the time complexity of Longest Common Prefix?

Both scans run in O(S) time, where S is the total number of letters in all the words, and need only O(1) extra memory besides the answer. The column scan is also bounded by n × (L+1) , where L is the length of the answer, so it stops early when the words disagree near the start.

Q: What should Longest Common Prefix return when there is no common prefix?

It returns the empty string "" . That happens as soon as two words start with different letters, as in stack , queue and heap .

Q: Which is better, horizontal or vertical scanning?

Both have the same worst case, O(S) . Vertical scanning, column by column, is the safer choice: it stops at the first column where any word disagrees, while horizontal scanning can compare a long prefix against many words before a late word cuts it short.

EasyArrays and strings

+10

You get an array of words strs. Return the longest string that every word starts with. If the words do not all begin with the same letter, return the empty string "". A word counts as a prefix of itself, so a single word is its own answer.

Function

longestCommonPrefix(strs: string-array) → string

strsstring-array: the words to compare
Returnsstring: the longest prefix all the words share, or an empty string

Constraints

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Every word contains only lowercase English letters.

Examples

Input: strs = ["interview", "internet", "interval", "internal"]
Output: "inter"
Explanation: All four words begin with inter. At the next position interview and interval have a v, internet and internal an n, so the prefix stops there.

Input: strs = ["stack", "queue", "heap"]
Output: ""
Explanation: The words start with s, q and h. They disagree on the very first letter, so no prefix is shared and the answer is empty.

Input: strs = ["prefix", "pre", "prepare"]
Output: "pre"
Explanation: pre is the shortest word and the other two begin with it, so it is the whole answer. A shared prefix can never be longer than the shortest word.

+19 hidden tests on Submit

Follow-up

Suppose the list stays fixed and you get many query words. How would you find, for each query, the longest prefix it shares with at least one word in the list, without rescanning the list each time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A letter belongs to the answer only if every word has that same letter at the same position, and the answer ends at the first position where any word disagrees or runs out. Both approaches below read the words letter by letter; they differ in the order they read them. Scanning by column stops at the first disagreement, so it never reads further than the answer plus one column.

Shrink the prefix word by word

Intuition

Start by assuming the whole first word is the answer. Then compare it with the second word letter by letter and cut it down to the part they share. Compare what is left with the third word, and so on. After the last word, what remains is common to all of them.

This is correct because the common prefix of many words is the common prefix of the first two, then of that result and the third word, and so on: each step can only keep or shorten it. For interview, internet, interval, internal, the candidate goes from interview to inter after the second word and stays there.

Every letter is compared at most once, so the time is O(S), where S is the total number of letters. You only keep a length, not a copy. The weak spot is order: with 200 words of 200 letters where the first 199 words agree and only the last one differs at its first letter, you compare all 200 letters against each of the first 199 words, close to 40,000 comparisons, before the last word cuts the prefix to nothing.

Algorithm

Set prefixLen to the length of strs[0].
For each other word, count how many leading letters it shares with strs[0], up to prefixLen.
Set prefixLen to that count, and stop early if it reaches 0.
Return the first prefixLen letters of strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Compare column by column

Intuition

Read the words like a table, one column at a time. Column 0 holds the first letter of every word, column 1 the second, and so on. Take the letter of strs[0] in the current column and check that every other word has the same letter there. The first time a word disagrees, or is too short to have that column at all, the answer is strs[0] up to that column.

The answer is exactly the run of columns where all words agree, and this loop walks those columns from the left and stops at the first one that breaks the run. If no column breaks it, strs[0] itself is the answer; it is then the shortest word or tied with it.

The loop reads at most one column past the answer, so with n words and an answer of length L it makes at most n × (L+1) checks, and it never reads the same letter of a word twice, so it is also O(S). In the case above, where 199 words agree and the last word differs at its first letter, it stops after the first column: 199 comparisons instead of close to 40,000.

Algorithm

Let first be strs[0].
For each column col from 0 to the length of first minus one, read first[col].
For each other word, if it has no letter at col or its letter differs, return the first col letters of first.
If every column matches, return first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Pitfalls and edge cases

The answer is short and the bugs sit at its end.

Reading past the end of a shorter word. In prefix, pre, prepare, column 3 exists in prefix but not in pre; check the length before you read the letter.
Comparing only the first and the last word in the given order. That shortcut needs the words sorted first: in abc, xbd, abd the first and the last share ab, but xbd breaks column 0 and the answer is empty.
Returning null or a placeholder when nothing is shared. The answer is the empty string.
Forgetting that a single word is its own prefix: algorithm alone returns algorithm.
Building the answer by adding one letter at a time to an immutable string. For a 200 letter answer that is 200 copies; keep a length and cut the first word once at the end.

Frequently asked questions4

What is the time complexity of Longest Common Prefix?

Both scans run in O(S) time, where S is the total number of letters in all the words, and need only O(1) extra memory besides the answer. The column scan is also bounded by n × (L+1), where L is the length of the answer, so it stops early when the words disagree near the start.

Can you find the longest common prefix by sorting the words?

Yes. In alphabetical order, every word that sits between the first and the last word starts with whatever those two share, so comparing only the first and the last word gives the answer. The sort compares about n log n pairs of words, which costs more than one scan, but the code is short.

What should Longest Common Prefix return when there is no common prefix?

It returns the empty string "". That happens as soon as two words start with different letters, as in stack, queue and heap.

Which is better, horizontal or vertical scanning?

Both have the same worst case, O(S). Vertical scanning, column by column, is the safer choice: it stops at the first column where any word disagrees, while horizontal scanning can compare a long prefix against many words before a late word cuts it short.

Python

def longestCommonPrefix(strs):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

strs = ["interview", "internet", "interval", "internal"]

Expected

"inter"