Hey everyone! Mahdi Shamlou here — back with another LeetCode classic problem.
Today, we're going to solve LeetCode #14: Longest Common Prefix.
This problem is interesting because we need to find the longest prefix shared by all strings in an array.
At first, it might look like a simple string comparison problem, but we need to think about how to compare multiple strings efficiently.
Let's get started!
1. Understanding the Problem
We are given an array of strings, and our task is to find the longest common prefix among all of them.
A prefix is simply a sequence of characters at the beginning of a string.
For example:
strs = ["flower", "flow", "flight"]
Let's look at these strings:
- flower
- flow
- flight
All three strings start with fl.
However, the third character is different:
- flower → o
- flow → o
- flight → i
So, the longest common prefix is:
fl
If there is no common prefix between the strings, we should return an empty string.
For example:
strs = ["dog", "racecar", "car"]
The result is:
""
Our goal is to find the longest sequence of characters that exists at the beginning of every string.
2. My Approach
My first idea was to find the shortest string in the input array.
Why?
Because the longest common prefix cannot be longer than the shortest string.
For example:
strs = ["flower", "flow", "flight"]
The shortest string is:
flow
There is no reason to check more characters than the length of this string.
After finding the shortest string, we can compare its characters with the characters at the same positions in all other strings.
I decided to use two steps:
- Find the shortest string manually.
- Compare characters at the same positions across all strings.
This approach is called Vertical Scanning.
3. Finding the Shortest String
First, we need to handle an important edge case.
What happens if the input array is empty?
We simply return an empty string:
if not strs:
return ""
Now, we need to find the shortest string.
Instead of using Python's built-in min() function, I decided to find it manually.
First, we assume that the first string is the shortest:
shortest = strs[0]
Then, we iterate through all strings and compare their lengths:
for word in strs:
if len(word) < len(shortest):
shortest = word
Whenever we find a shorter string, we update our shortest variable.
After this loop, we know that shortest contains the shortest string in the input array.
4. Vertical Scanning
Now comes the most important part of the solution.
We already know the shortest string, so we can use its length to determine how many positions we need to check.
We start from the first character and move forward.
For every position, we compare that character with the corresponding character in all other strings.
For example:
strs = ["flower", "flow", "flight"]
Let's visualize the comparison:
Position 0:
flower -> f
flow -> f
flight -> f
All characters match!
Now we move to the next position:
Position 1:
flower -> l
flow -> l
flight -> l
All characters match!
Let's move to position 2:
Position 2:
flower -> o
flow -> o
flight -> i
Characters don't match!
At this point, we know that the common prefix ends before position 2.
So, we return:
shortest[:2]
Which gives us:
fl
This is why we use two nested loops:
- The outer loop moves through character positions.
- The inner loop compares the character at that position across all strings.
If we find a mismatch, we immediately return the common prefix.
5. My Final Python Solution
Here is my final implementation:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
# ind the shortest string manually
shortest = strs[0]
for word in strs:
if len(word) < len(shortest):
shortest = word
# vertical scaning
for i in range(len(shortest)):
for word in strs:
if word[i] != shortest[i]:
return shortest[:i]
return shortest
6. How Does It Work?
Let's use the same example:
strs = ["flower", "flow", "flight"]
First, we find the shortest string:
shortest = "flow"
Its length is 4, so we only need to check four positions.
Let's see what happens at each iteration:
| Position | flower | flow | flight | Result |
|---|---|---|---|---|
| 0 | f | f | f | Match |
| 1 | l | l | l | Match |
| 2 | o | o | i | Mismatch |
At position 2, we find a mismatch.
Therefore, we execute:
return shortest[:2]
And the final result is:
"fl"
Notice that we don't need to check the remaining characters.
As soon as we find a mismatch, we already know the answer.
7. Complexity Analysis
Let's analyze the solution.
Time Complexity: O(S)
Let:
-
nbe the number of strings. -
mbe the length of the shortest string. -
Sbe the total number of characters across all strings.
First, we iterate through all strings to find the shortest one.
This takes O(n) time.
Then, we compare characters using two nested loops.
In the worst case, we compare every character of the shortest string across all strings.
This takes O(n × m) time.
Therefore, the total time complexity is:
O(n + n × m)
Since the shortest string has at least one character when the input strings are non-empty, this is bounded by:
O(S)
Space Complexity: O(1)
We only use a few variables:
shortestwordi
We don't create any additional data structures that grow with the input size.
Therefore, the auxiliary space complexity is O(1).
Final Thoughts
This problem reminded me that sometimes we don't need complicated algorithms to solve string problems.
Finding the shortest string first helped reduce the number of positions we needed to check.
Then, using Vertical Scanning allowed us to compare all strings position by position.
I also liked this approach because we can stop immediately when we find the first mismatch.
What do you think about this approach? Would you use Vertical Scanning, or would you try another method?
Let me know in the comments!
You can also find my LeetCode solutions in my GitHub repository:
GitHub: mahdi0shamlou/LeetCode
Author: Mahdi Shamlou
Author: مهدی شاملو


Top comments (0)