DEV Community

Mahdi SHamlou | مهدی شاملو
Mahdi SHamlou | مهدی شاملو

Posted on Edited on

Mahdi Shamlou | Solving LeetCode #14: Longest Common Prefix — Step by Step

Hey everyone! Mahdi Shamlou here — back with another LeetCode classic problem.

Mahdi Shamlou

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!

Mahdi Shamlou

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"]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

If there is no common prefix between the strings, we should return an empty string.

For example:

strs = ["dog", "racecar", "car"]
Enter fullscreen mode Exit fullscreen mode

The result is:

""
Enter fullscreen mode Exit fullscreen mode

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"]
Enter fullscreen mode Exit fullscreen mode

The shortest string is:

flow
Enter fullscreen mode Exit fullscreen mode

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:

  1. Find the shortest string manually.
  2. 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 ""
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

Then, we iterate through all strings and compare their lengths:

for word in strs:
    if len(word) < len(shortest):
        shortest = word
Enter fullscreen mode Exit fullscreen mode

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"]
Enter fullscreen mode Exit fullscreen mode

Let's visualize the comparison:

Position 0:

flower -> f
flow   -> f
flight -> f

All characters match!
Enter fullscreen mode Exit fullscreen mode

Now we move to the next position:

Position 1:

flower -> l
flow   -> l
flight -> l

All characters match!
Enter fullscreen mode Exit fullscreen mode

Let's move to position 2:

Position 2:

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

Characters don't match!
Enter fullscreen mode Exit fullscreen mode

At this point, we know that the common prefix ends before position 2.

So, we return:

shortest[:2]
Enter fullscreen mode Exit fullscreen mode

Which gives us:

fl
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

6. How Does It Work?

Let's use the same example:

strs = ["flower", "flow", "flight"]
Enter fullscreen mode Exit fullscreen mode

First, we find the shortest string:

shortest = "flow"
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

And the final result is:

"fl"
Enter fullscreen mode Exit fullscreen mode

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:

  • n be the number of strings.
  • m be the length of the shortest string.
  • S be 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)
Enter fullscreen mode Exit fullscreen mode

Since the shortest string has at least one character when the input strings are non-empty, this is bounded by:

O(S)
Enter fullscreen mode Exit fullscreen mode

Space Complexity: O(1)

We only use a few variables:

  • shortest
  • word
  • i

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)