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, with O(1) extra memory besides the answer. The column scan is also bounded by n × (L+1) for an answer of length L , so it stops early when the words disagree near the start.

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

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 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 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.

Follow-up

Suppose the list stays fixed and many query words arrive. How would you find each query's longest prefix shared with some word in the list, without rescanning the list?

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 it at the same position, and the answer ends at the first position where a word disagrees or runs out. Both approaches read the words letter by letter in a different order. Scanning by column stops at the first disagreement.

Shrink the prefix word by word

Intuition

Assume the whole first word is the answer. Cut it down to the part it shares with the second word, then with the third, and so on. The common prefix of many words is the common prefix of the first two, then of that and the third word: each step can only keep or shorten it. For example 1, 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) for S letters in all. The weak spot is order: with 200 words of 200 letters where only the last word differs at its first letter, you make 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. 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, 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 that run from the left and stops where it breaks. If nothing breaks it, strs[0] is the answer.

With n words and an answer of length L, the loop makes at most n × (L+1) checks, which is also O(S). In the case where only the last of 200 words differs at its first letter, it stops after 199 comparisons.

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

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 without sorting. In abc, xbd, abd those two 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.
Adding one letter at a time to an immutable string. A 200 letter answer then costs 200 copies; keep a length and cut the first word once.

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, with O(1) extra memory besides the answer. The column scan is also bounded by n × (L+1) for an answer of length L, 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 between the first and the last starts with whatever those two share, so comparing only those two 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?

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 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.

def longestCommonPrefix(strs):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

"inter"