Longest Common Prefix

easyFREEArrays & StringsMicrosoft DSA

Given an array of strings, find the longest common prefix among all strings. If none, return "".

Example

Input

flower,flow,flight

Output

fl

Reasoning

Input: a list of words, here flower, flow and flight (lengths 6, 4 and 6). A prefix is the first $k$ letters of a word; the answer is the largest $k$ for which all three words begin with the same $k$ letters.
Upper bound: a shared prefix can never be longer than the shortest word, so here $k \le 4$ (the length of flow).
Position 1: the words start with f, f, f. All agree, so $k \ge 1$ .
Position 2: l, l, l. Still unanimous, so $k \ge 2$ .
Position 3: o, o, i. flight disagrees, so no prefix of length 3 is shared by everyone, and nothing longer can be either. Hence $k = 2$ and the output is fl.
Notice: one disagreeing word is enough to cap the answer. For the words dog, racecar and car the very first letters differ, so $k = 0$ and the result is the empty string; a list holding only abc returns abc itself.

Constraints

1 <= len(strs) <= 200
0 <= len(strs[i]) <= 200
strs[i] consists of lowercase English letters

More from Microsoft DSA

FizzBuzzeasy Roman to Integereasy Reverse Integermedium Pow(x, n)medium Implement Stack using Queueseasy

Concept primer

Background Knowledge

The longest common prefix problem is a classic example of a string processing task. To tackle this problem, it's essential to understand the basics of string manipulation and comparison. In programming, strings are sequences of characters, and comparing strings involves checking the similarity between these sequences. The longest common prefix is the longest sequence of characters that appears at the beginning of all strings in a given array.

In the context of this problem, we need to consider how to iterate through the characters of each string and compare them to find the common prefix. This involves understanding the concept of indexing, where each character in a string is assigned a unique position or index. We can use this indexing to access and compare characters across different strings. Additionally, it's crucial to think about how to handle edge cases, such as an empty array or strings with varying lengths.

The longest common prefix problem also touches on the idea of pattern recognition and matching. We need to identify the pattern that appears at the beginning of all strings and determine its length. This requires a systematic approach to comparing characters and updating our understanding of the common prefix as we iterate through the strings.

Algorithm/Approach

The general approach to solving the longest common prefix problem involves using a iterative comparison technique. We can iterate through the characters of each string, comparing them to find the common prefix. One common algorithm pattern used to solve this type of problem is the vertical scanning approach, where we compare the characters at the same position across all strings.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty string to store the longest common prefix
Iterate through the characters of the first string in the array
For each character, compare it to the corresponding character in all other strings
If all characters match, add the character to the longest common prefix
If a mismatch is found, break the loop and return the longest common prefix
Handle edge cases, such as an empty array or strings with varying lengths

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly handling edge cases, such as an empty array or strings with varying lengths
Failing to update the longest common prefix correctly when a mismatch is found
Using an inefficient comparison technique, leading to poor performance

Time & Space Complexity

The expected time complexity for this problem is O( $n \cdot m$ ), where $n$ is the length of the array and $m$ is the length of the shortest string. The space complexity is O( $m$ ), as we need to store the longest common prefix, which can be at most $m$ characters long.

solution.py

Python 3.13

Test results