Leetcode – Longest Common Prefix

Spread the love

String manipulation is a key aspect of many coding interviews and problems, and understanding how to efficiently work with strings can set you apart from other candidates. One such problem that helps strengthen these string manipulation skills is the “Longest Common Prefix” problem from LeetCode.

This article will explore the problem in depth, analyze various strategies to solve it, and provide Python-based solutions with an explanation of their workings.

Problem Statement

LeetCode Problem #14: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”.

Example

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

The problem is fairly straightforward: we are given an array of strings, and we need to find the longest common prefix among all strings.

Approach 1: Horizontal Scanning

The first and most intuitive approach is to compare strings one by one. We first take the entire first string as the prefix, then we compare it with the second string and shorten the prefix if necessary. We then compare the updated prefix with the third string, and so on.

Here’s a Python function implementing this approach:

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    prefix = strs[0]
    for string in strs[1:]:
        while string[:len(prefix)] != prefix:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

In this function, we initialize the prefix to the first string. We then iterate over the other strings in the list. For each string, we check if it starts with the current prefix. If it doesn’t, we shorten the prefix by one character and check again, repeating this process until we find a common prefix or exhaust the prefix.

The time complexity of this solution is O(S), where S is the sum of all characters in all strings. In the worst case scenario, we perform S character comparisons, which happens when all strings are the same.

Approach 2: Vertical Scanning

Instead of comparing strings one by one, we can compare characters at the same index in all strings. We scan through each character of the first string and check if all strings have that character at the same index. As soon as we find a mismatch, we can return the prefix found so far.

Here’s a Python function implementing this approach:

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    for i in range(len(strs[0])):
        char = strs[0][i]
        for j in range(1, len(strs)):
            if i == len(strs[j]) or strs[j][i] != char:
                return strs[0][:i]
    return strs[0]

In this function, we iterate over each character of the first string. For each character, we check if all other strings have the same character at the same index. If they don’t, we return the prefix up to but not including the current index. If we complete the loop without finding a mismatch, we return the entire first string as the prefix.

The time complexity of this solution is also O(S), where S is the sum of all characters in all strings. In the worst case, we perform S character comparisons, which happens when the shortest string is a prefix of all other strings.

Approach 3: Binary Search

The third approach is to apply binary search to find the longest common prefix. This is possible because if a string S is a common prefix of all strings, then any substring of S (from the beginning) is also a common prefix.

The idea is to take the shortest string as the potential prefix, and apply binary search to check whether the prefix exists in all strings. If it does, we check the right half; if it doesn’t, we check the left half. We continue this process until we find the longest common prefix.

Here’s a Python function implementing this approach:

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    shortest_str = min(strs, key=len)
    low, high = 0, len(shortest_str)
    
    while low <= high:
        mid = (low + high) // 2
        if all(s[:mid] == shortest_str[:mid] for s in strs):
            low = mid + 1
        else:
            high = mid - 1
    
    return shortest_str[:high]

In this function, we first find the shortest string, because the length of the common prefix cannot be longer than this string. We then apply binary search to check whether the prefix of length mid exists in all strings. If it does, we continue to check the right half; if it doesn’t, we continue to check the left half. The process continues until low exceeds high, and we return the prefix of length high.

The time complexity of this solution is O(S*log(n)), where S is the sum of all characters in all strings, and n is the length of the shortest string. This is because in the worst case, we perform S character comparisons for each of the log(n) iterations of binary search.

Conclusion

The Longest Common Prefix problem is a great exercise in string manipulation and algorithmic thinking. It shows how a seemingly simple problem can be tackled in multiple ways, each with its own trade-offs. The Python solutions provided here demonstrate these approaches and provide a foundation for solving more complex string-related problems.

Leave a Reply