#14

Easy

LeetCode Problem Workspace

Longest Common Prefix

Find the longest common prefix in an array of strings, returning an empty string if none exists.

Problem Statement

You are given an array of strings. Your task is to find the longest common prefix among these strings. If no such prefix exists, return an empty string.

For example, given the array ['flower', 'flow', 'flight'], the longest common prefix is 'fl'. If no prefix is found, such as in ['dog', 'racecar', 'car'], return an empty string.

Examples

Example 1

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

Output: "fl"

Example details omitted.

Example 2

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

Output: ""

There is no common prefix among the input strings.

Constraints

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.

Solution Approach

Vertical Scanning

In the vertical scanning approach, we check each column (character) across all strings. For each position in the strings, we compare the character in that position. As soon as we encounter a mismatch, we return the common prefix found up to that point. The time complexity depends on the number of strings and the length of the shortest string.

Horizontal Scanning

The horizontal scanning approach compares the first string with the rest one by one. We initialize the prefix to the first string and then progressively reduce the prefix by comparing it with each subsequent string. This method is straightforward and works efficiently for shorter arrays. The complexity depends on the length of the strings and the number of comparisons.

Using Divide and Conquer

The divide and conquer approach splits the array of strings into two halves. Each half is processed recursively, and the common prefix for the two halves is determined. This approach leverages the efficiency of the divide and conquer pattern, cutting the problem size in half at each step. Its complexity is typically O(m * log n), where m is the length of the longest string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the problem varies depending on the approach. For vertical scanning, it is O(m * n), where m is the length of the shortest string and n is the number of strings. For horizontal scanning, the complexity is also O(m * n). The divide and conquer approach runs in O(m * log n) time, where m is the maximum string length and n is the number of strings. Space complexity depends on the solution, but is O(1) for vertical and horizontal scanning.

What Interviewers Usually Probe

Do you understand how to handle edge cases like when there is no common prefix?
Can you describe the trade-offs between vertical scanning and horizontal scanning?
Will you be able to choose the most efficient approach based on the input size?

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where no common prefix exists, returning an empty string instead of a valid result.
Not accounting for the possibility of empty strings in the input, which can break certain approaches if not handled carefully.
Incorrectly assuming that all strings must have a non-zero length; the edge case where an input array has an empty string should be checked.

Follow-up variants

How would you optimize the solution for very large input sizes, say up to a million strings?
Can you modify the solution to find the longest common suffix instead of the prefix?
How would the problem change if strings could contain uppercase letters or other characters?

FAQ

What is the Longest Common Prefix problem?

The Longest Common Prefix problem asks you to find the longest prefix that all strings in a given array share. If no such prefix exists, return an empty string.

What is the most efficient approach to solving the Longest Common Prefix?

Vertical scanning is often the simplest and most efficient for small inputs, while divide and conquer is optimal for larger inputs. The choice depends on input size and constraints.

What are the edge cases for the Longest Common Prefix problem?

Edge cases include arrays with no common prefix, arrays with one string, arrays with empty strings, and strings with varying lengths.

How does the time complexity change with input size?

The time complexity of the solution depends on both the number of strings and the length of the shortest string, typically O(m * n) where m is the string length and n is the number of strings.

How do you handle inputs where some strings are empty?

If any string is empty, the result is immediately an empty string since there is no common prefix. This should be checked before processing the strings.

terminal

Solution

Solution 1: Character Comparison

We use the first string $strs[0]$ as a benchmark, and compare whether the $i$-th character of the subsequent strings is the same as the $i$-th character of $strs[0]$. If they are the same, we continue to compare the next character. Otherwise, we return the first $i$ characters of $strs[0]$.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(len(strs[0])):
            for s in strs[1:]:
                if len(s) <= i or s[i] != strs[0][i]:
                    return s[:i]
        return strs[0]

Continue Practicing

#139 word break #140 word break ii #212 word search ii