LeetCode 14: Longest Common Prefix

Problem Restatement

We are given an array of strings strs.

We need to find the longest string that appears at the beginning of every string in the array.

If there is no common prefix, return an empty string.

For example:

["flower", "flow", "flight"]

All strings start with:

"fl"

So the answer is:

"fl"

The LeetCode statement asks for the longest common prefix string among an array of strings, returning "" when no common prefix exists.

Input and Output

Example function shape:

def longestCommonPrefix(strs: list[str]) -> str:
    ...

Examples

Example 1:

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

Compare characters from the start:

flower
flow
flight

The first character is f in every string.

The second character is l in every string.

At the third character:

flower -> o
flow   -> o
flight -> i

They differ.

Output:

"fl"

Example 2:

strs = ["dog", "racecar", "car"]

The first characters are:

d
r
c

They already differ.

Output:

""

Example 3:

strs = [""]

The only string is empty.

Output:

""

First Thought: Shrink a Candidate Prefix

A simple approach is to start with the first string as the candidate prefix.

Then compare it with every other string.

Whenever a string does not start with the current prefix, remove the last character from the prefix.

Code:

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        prefix = strs[0]

        for word in strs[1:]:
            while not word.startswith(prefix):
                prefix = prefix[:-1]

                if prefix == "":
                    return ""

        return prefix

This works, but repeated slicing can create extra string copies.

We can solve it more directly by comparing characters column by column.

Key Insight

A common prefix must match at the same index in every string.

So we can use the first string as a reference.

For each index i in the first string:

1. Read strs[0][i].
2. Check whether every other string has the same character at index i.
3. If any string is too short or has a different character, return strs[0][:i].

This stops exactly where the common prefix ends.

Visual Walkthrough

Use:

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

Use "flower" as the reference.

Index 0:

flower[0] = f
flow[0]   = f
flight[0] = f

All match.

Index 1:

flower[1] = l
flow[1]   = l
flight[1] = l

All match.

Index 2:

flower[2] = o
flow[2]   = o
flight[2] = i

Mismatch.

Return:

strs[0][:2] = "fl"

Algorithm

1. Choose the first string as the reference.
2. For each index i in the reference:
   • compare the character at index i with every other string
   • if another string has ended, return the prefix before i
   • if another string has a different character, return the prefix before i
3. If all characters in the first string match, return the first string.

Correctness

The algorithm checks prefix characters from left to right.

For every index before the stopping point, all strings have the same character. Therefore strs[0][:i] is a common prefix.

The algorithm stops at the first index where at least one string either has no character or has a different character. No longer prefix can be common, because a longer prefix would need all strings to match at that index.

If the algorithm never stops, then every character of the first string appears at the beginning of every other string. So the first string itself is the longest common prefix.

Therefore the algorithm returns exactly the longest common prefix.

Complexity

Here S is the total number of characters inspected. In the worst case, this is the total length of all strings.

Implementation

class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first

Code Explanation

Use the first string as the reference:

first = strs[0]

Scan each character of the reference:

for i, char in enumerate(first):

Compare that character with the same position in every other word:

for word in strs[1:]:

If a word is shorter, the common prefix ends before index i:

i == len(word)

If the character differs, the common prefix also ends before index i:

word[i] != char

So we return:

return first[:i]

If the loop completes, the whole first string is common to all strings:

return first

Testing

def run_tests():
    s = Solution()

    assert s.longestCommonPrefix(["flower", "flow", "flight"]) == "fl"
    assert s.longestCommonPrefix(["dog", "racecar", "car"]) == ""
    assert s.longestCommonPrefix([""]) == ""
    assert s.longestCommonPrefix(["a"]) == "a"
    assert s.longestCommonPrefix(["ab", "a"]) == "a"
    assert s.longestCommonPrefix(["same", "same", "same"]) == "same"
    assert s.longestCommonPrefix(["cir", "car"]) == "c"

    print("all tests passed")

run_tests()