LeetCode Problem

Problem Description

Write a function to find the longest common prefix string amongst an array of strings.

Examples

Input: flower,flow,flight
Output: fl

Input: dog,racecar,car
Output:

Constraints

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

Follow-up

Approach to Solve

Iterate through characters of the first string, comparing with other strings.

Code Implementation

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

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string prefix = strs[0];
        for (int i = 1; i < strs.size(); ++i) {
            while (strs[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) return "";
            }
        }
        return prefix;
    }
};

Explanation

The Longest Common Prefix problem is solved using a character-by-character matching approach. Here's a detailed explanation of the solution:

Edge case handling:
- If the input array is empty, return an empty string.
Python approach: a. Find the shortest string in the array, as the longest common prefix cannot be longer than this. b. Iterate through each character of the shortest string. c. For each character, compare it with the corresponding character in all other strings. d. If a mismatch is found, return the prefix up to that point. e. If we complete the loop, the entire shortest string is the common prefix.
Java and C++ approach: a. Start with the first string as the initial prefix. b. Iterate through the remaining strings. c. For each string, while it doesn't start with the current prefix:
- Shorten the prefix by removing the last character.
- If the prefix becomes empty, return an empty string. d. After processing all strings, return the final prefix.
Time Complexity: O(S), where S is the sum of all characters in all strings.
- In the worst case, we might compare all characters of all strings.
Space Complexity: O(1) or O(S), depending on whether we consider the space for the output string.
- We only use a constant amount of extra space, not counting the space for the result.

This approach is efficient as it minimizes unnecessary comparisons by updating the prefix as soon as a mismatch is found. It works well for both small and large sets of strings, handling edge cases like empty inputs or no common prefix gracefully.

Complexity

Time Complexity: O(S)
Space Complexity: O(1)