LeetCode #14: Longest Common Prefix

Hello, coding enthusiasts! Today, we’re solving the “Longest Common Prefix” problem from LeetCode using Python and JavaScript.

Problem Statement

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 1:

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

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

Analysis

The problem is straightforward. We need to find the longest common prefix among all the strings. The prefix is a sequence of characters at the beginning of each string.

Approach

Here’s a step-by-step approach to solve this problem:

Initialize Prefix: We start with the prefix as the first string in the array.
Iterate Over Strings: We iterate over each string in the array, starting from the second string.
Check Prefix: We check if the current string starts with the prefix. If it doesn’t, we remove the last character from the prefix.
Update Prefix: We continue removing the last character from the prefix until the current string starts with the prefix. If the prefix becomes an empty string, we return it.
Return Prefix: After iterating over all the strings, the prefix will be the longest common prefix. We return this prefix as the result.

Time Complexity

The time complexity of this approach is O(n*m), where n is the number of strings and m is the length of the largest string. This is because in the worst case, we are comparing m characters n times.

Space Complexity

The space complexity is O(1), because we are not using any additional space that scales with the input size.

Code

Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        shortest_str = min(strs, key=len)
        for i, char in enumerate(shortest_str):
            for other in strs:
                if other[i] != char:
                    return shortest_str[:i]
        return shortest_str

JavaScript

var longestCommonPrefix = function(strs) {
    if (!strs.length) return '';
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (!prefix.length) return '';
        }
    }
    return prefix;
};

Conclusion

In conclusion, the “Longest Common Prefix” problem is a great example of how we can apply simple string manipulation techniques to solve problems in computer science.

The solution has a time complexity of O(n*m) and a space complexity of O(1), making it highly efficient.

Happy coding!

Learn More: