LeetCode 14 Solution: Longest Common Prefix in Python

The LeetCode 14 solution to the “Longest Common Prefix” problem challenges you to find the longest prefix shared by a group of strings. A prefix is a substring that appears at the start of a string. The task is to determine the longest prefix that is common across all strings in the array. If no common prefix exists, the function should return an empty string.

This problem is fundamental for string manipulation in Python and is frequently asked in coding interviews. In this post, we’ll explore two efficient solutions to tackle this problem using different techniques: horizontal scanning and a sorting-based approach. Both of these methods are easy to understand and implement, making it easier to apply the LeetCode 14 solution successfully.

Problem Breakdown

Let’s break down the problem to ensure we understand it correctly. Suppose we have an input array of strings like ["flower", "flow", "flight"]. In this case, the longest common prefix is "fl". On the other hand, if the input is ["dog", "racecar", "car"], there is no common prefix, and the result will be an empty string "".

The challenge lies in finding this common prefix efficiently, especially when you are dealing with up to 200 strings, each with a length of up to 200 characters. Let’s dive into two different ways to solve this problem.

Approach 1: Horizontal Scanning

The horizontal scanning approach works by comparing each string in the array one by one, reducing the prefix gradually until it matches with every string.

We begin by assuming that the first string in the list is the common prefix. Then, we compare this prefix with each of the other strings. If a mismatch is found, the prefix is shortened by removing characters from the end. This process continues until the prefix is either fully reduced to match all strings or becomes an empty string, meaning no common prefix exists.

Python Code for Horizontal Scanning:

def longestCommonPrefix(strs):
    if not strs:
        return ""

    # Assume the first string is the prefix
    prefix = strs[0]

    # Compare the prefix with each string
    for s in strs[1:]:
        # Keep reducing the prefix until it matches
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""

    return prefix

In this solution, we compare the prefix with each string one by one, and if there’s a mismatch, we keep shortening the prefix until it matches the beginning of all strings. This method is efficient and works well within the problem’s constraints. If the list of strings is empty, the function will return an empty string immediately.

Approach 2: Sorting-Based Solution

Another effective method to solve the LeetCode 14 problem is by using a sorting-based approach. The idea here is to first sort the array of strings. Once sorted, the smallest and largest strings (in lexicographical order) will have the least in common, so comparing only these two extremes will reveal the longest common prefix.

After sorting the array, we compare the first and last strings character by character. Since they represent the most different strings, finding the common prefix between them is sufficient to cover all strings in the array.

Python Code for Sorting-Based Solution:

def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs:
        return ""
    
    res = ""

    strs = sorted(strs)
    first = strs[0]
    last = strs[-1]
    r = min(len(first), len(last))

    for i in range(r):
        if (first[i] != last[i]):
            return res

        res += first[i]

    return res

In this approach, sorting the strings brings the lexicographically smallest string to the front and the largest to the end of the list. By comparing just these two, we can find the longest common prefix. If at any point the characters don’t match, the comparison stops, and the current prefix is returned. This approach can be especially efficient when the strings have varying degrees of similarity.

Which Solution is Better?

Both solutions are valid and work well, but each has its own strengths depending on the scenario:

• The horizontal scanning method works by comparing each string one by one. It’s simple and efficient, especially when the common prefix is short or when there are many strings with similar prefixes. It has a time complexity of *O(n m)**, where n is the number of strings and m is the length of the shortest string.

• The sorting-based solution takes advantage of sorting the strings first. After sorting, the common prefix is only compared between the first and last strings, which makes it slightly more efficient in some cases. However, sorting adds an extra cost of O(n log n), making this approach potentially slower when the list is large.

Final Thoughts

The LeetCode 14 solution can be approached using different techniques depending on the input data. The horizontal scanning approach is intuitive and performs well for most input sizes. On the other hand, the sorting-based solution offers an interesting alternative by reducing the comparison to just two strings. Both solutions are easy to understand and implement, making them useful for tackling string problems efficiently.

By mastering both approaches, you’ll be better prepared for coding challenges that involve string manipulation, and you’ll have a deeper understanding of how to optimize your algorithms for different problem scenarios. Whether you’re preparing for interviews or just practicing algorithmic thinking, solving the LeetCode 14 problem will strengthen your skills in handling common prefix problems in Python.

Happy Coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.