LeetCode 14: Longest Common Prefix Solution in Python Explained

Problem Statement

LeetCode 14, Longest Common Prefix, is an easy-level challenge where you’re given an array of strings strs and need to find the longest common prefix shared by all of them. A prefix is the starting part of each string, and the goal is to return this common portion as a string. If no common prefix exists, return an empty string (""). The array always has at least one string, and each string contains only lowercase English letters, making it a straightforward yet practical problem to solve.

Constraints

1 <= strs.length <= 200: Array length ranges from 1 to 200 strings.
0 <= strs[i].length <= 200: Each string’s length is between 0 and 200 characters.
strs[i] consists of only lowercase English letters.

Example

Input: strs = ["flower", "flow", "flight"]
Output: "fl"
Explanation: "fl" is the longest prefix all three strings share.

Input: strs = ["dog", "racecar", "car"]
Output: ""
Explanation: No common prefix exists among these strings.

Input: strs = ["interspecies", "interstellar", "interstate"]
Output: "inters"
Explanation: "inters" is the longest common prefix across all three.

Understanding the Problem

How do you solve LeetCode 14: Longest Common Prefix in Python? Imagine you’re comparing a bunch of words to find what they all start with. For ["flower", "flow", "flight"], the prefix "fl" fits all three, but "flo" doesn’t because "flight" diverges at the third letter. We need a method to check each character position across all strings, stopping when they differ or a string ends. We’ll use a vertical scanning approach, comparing characters column-by-column, to find this shared starting piece efficiently.

Solution: Vertical Scanning

Explanation

This method compares characters across all strings at each position, building the prefix as long as they match. It’s like lining up the strings and reading down each column until something doesn’t align.

Here’s a quick visual for ["flower", "flow", "flight"]:

f l o w e r
f l o w
f l i g h t
↓ ↓ ↓
f l   (stop at 'i' vs 'o')

Handle Edge Case.

If the array is empty, return an empty string right away.

Use First String as Base.

Take the first string as a starting point to compare with others.

Scan Vertically.

For each character position in the first string:

Check if all strings have that character and it matches.
If they do, add it to the prefix.
If not, or a string ends, stop.

Return Result.

Return the prefix built so far.

Step-by-Step Example

Example 1: strs = ["flower", "flow", "flight"]

We have ["flower", "flow", "flight"] and want to find "fl".

Goal: Find the longest prefix all three strings share.
Result for Reference: "fl" is the common start.
Start: Begin with an empty result string. Use "flower" as the base since it’s the first string.
Step 1: Check position 0 (first character).

"flower"[0] = "f".
"flow"[0] = "f".
"flight"[0] = "f".
All match with "f", so add "f" to the result.
Result = "f".

Step 2: Check position 1 (second character).

"flower"[1] = "l".
"flow"[1] = "l".
"flight"[1] = "l".
All match with "l", add "l".
Result = "fl".

Step 3: Check position 2 (third character).

"flower"[2] = "o".
"flow"[2] = "o".
"flight"[2] = "i".
They don’t match ("o" ≠ "i"), so stop here.

Finish: Result is "fl".

Return "fl", the longest common prefix.

Example 2: strs = ["dog", "racecar", "car"]

Now, we have ["dog", "racecar", "car"].

Goal: Find any common prefix.
Result for Reference: No common prefix, so "".
Start: Result empty, base is "dog".
Step 1: Position 0.

"dog"[0] = "d".
"racecar"[0] = "r".
"car"[0] = "c".
Mismatch ("d" ≠ "r"), stop immediately.

Finish: Result is "".

Return "", as there’s no shared prefix.

Example 3: strs = ["interspecies", "interstellar", "interstate"]

For ["interspecies", "interstellar", "interstate"], expecting "inters".

Goal: Find the longest common prefix.
Result for Reference: "inters".
Start: Result empty, base is "interspecies".
Step 1: Position 0.

"interspecies"[0] = "i", "interstellar"[0] = "i", "interstate"[0] = "i".
All "i", add "i".
Result = "i".

Step 2: Position 1.

All have "n", add "n".
Result = "in".

Step 3: Position 2.

All have "t", add "t".
Result = "int".

Step 4: Position 3.

All have "e", add "e".
Result = "inte".

Step 5: Position 4.

All have "r", add "r".
Result = "inter".

Step 6: Position 5.

All have "s", add "s".
Result = "inters".

Step 7: Position 6.

"interspecies"[6] = "p", "interstellar"[6] = "t", "interstate"[6] = "t".
Mismatch ("p" ≠ "t"), stop.

Finish: Result is "inters".

Return "inters", the longest shared prefix.

Code

Here’s the Python code to solve LeetCode 14: Longest Common Prefix. It’s clear, efficient, and works in Python 3.6+. Want to test it? Try it on Replit!

def longestCommonPrefix(strs: list[str]) -> str:
    # Handle empty array
    if not strs:
        return ""

    # Use first string as base
    for i in range(len(strs[0])):
        char = strs[0][i]
        # Compare with all other strings
        for s in strs[1:]:
            if i >= len(s) or s[i] != char:
                return strs[0][:i]
    # If no mismatch, first string is the prefix
    return strs[0]

Note: Dive deeper into Python’s string slicing in the official Python documentation.

Complexity

Time Complexity: O(S) – Where S is the total number of characters across all strings. In the worst case (e.g., all strings identical), we check every character of the first string against all others.
Space Complexity: O(1) – We only use a result string and a few variables, keeping space constant regardless of input size.

Efficiency Notes

This vertical scanning approach is highly efficient for LeetCode 14. It stops as soon as a mismatch occurs, avoiding unnecessary comparisons, and leverages the first string as a base to minimize overhead. It’s a practical solution that balances simplicity and performance.

Key Insights

Here are some tips to master LeetCode 14: Longest Common Prefix:

Leverage the First String: Starting with one string as a reference simplifies the logic—just trim it when needed.
Mind the Length: Always check if a position exceeds a string’s length to avoid errors.
Stop on Mismatch: The moment characters differ, you’ve found your limit—no need to keep going.

These insights make the problem feel intuitive and manageable!

Alternative: Horizontal Scanning (Brief Mention)

Explanation

An alternative is horizontal scanning, where you compare full prefixes across strings, starting with the first string and shortening it whenever it doesn’t match the next string. While it works, it can be slower for cases with early mismatches, as it checks entire prefixes instead of stopping at the first differing character. Vertical scanning is generally preferred for its efficiency, so we’ll stick with that.

Additional Example

For strs = ["abcd", "abc", "abcef"]:

Goal: Find the longest common prefix.
Result for Reference: "abc".
Start: Result empty, base "abcd".
Steps:

Position 0: All "a", Result = "a".
Position 1: All "b", Result = "ab".
Position 2: All "c", Result = "abc".
Position 3: "d" vs. end vs. "e", stop.

Finish: Return "abc".

Matches the shared "abc" prefix.

Edge Cases

Here are some edge cases to consider:

Single String: strs = ["flower"].

Returns "flower" (whole string is the prefix).

Empty Strings: strs = ["", "a"].

Returns "" (empty string limits the prefix).

All Identical: strs = ["aaa", "aaa", "aaa"].

Returns "aaa" (full match).

Shortest Limits: strs = ["a", "ab", "abc"].

Returns "a" (shortest string caps it).

These cases test the solution’s ability to handle boundaries, and our approach manages them all smoothly.

Final Thoughts

The vertical scanning method is a clean, efficient way to solve LeetCode 14: Longest Common Prefix in Python. It’s beginner-friendly, fast, and perfect for coding interviews, teaching you how to compare strings systematically. Want more string challenges? Check out our guide on LeetCode 13: Roman to Integer for another fun twist!