{x}
blog image

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 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 if it is non-empty.

Solution Explanation: Longest Common Prefix

This problem aims to find the longest common prefix among a list of strings. Several approaches can solve this, but a straightforward and efficient method involves character-by-character comparison.

Approach:

  1. Handle Edge Cases: If the input list is empty or contains only one string, the longest common prefix is either an empty string or the single string itself, respectively.

  2. Iterative Comparison: The algorithm iterates through the characters of the first string. For each character, it checks if that character exists at the same position in all other strings.

  3. Mismatch Detection: If a mismatch is found (a character at a given position differs between any two strings), the algorithm immediately stops and returns the common prefix found up to that point.

  4. Complete Match: If the loop completes without finding any mismatches, it means all strings share a common prefix up to the length of the first string. The first string is then returned as the longest common prefix.

Time and Space Complexity:

  • Time Complexity: O(S), where S is the sum of the lengths of all strings in the input list. In the worst-case scenario, the algorithm might need to traverse all characters of all strings before identifying a mismatch or completing the process. This is significantly better than O(n*m) where n is the number of strings and m is the length of the shortest string if we only consider the shortest string.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Examples (with explanations):

The code examples below demonstrate the solution in several popular programming languages. They all follow the same core logic described above. Note that slight variations might exist due to language-specific features.

Python:

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:  # Handle empty list
            return ""
        prefix = ""
        for i in range(len(strs[0])):  # Iterate through characters of the first string
            char = strs[0][i]
            for s in strs[1:]:  # Check against other strings
                if i >= len(s) or s[i] != char:  # Mismatch detected
                    return prefix
            prefix += char  # Append character if it's common
        return prefix

Java:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = "";
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            boolean match = true;
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    match = false;
                    break;
                }
            }
            if (match) prefix += c;
            else break;
        }
        return prefix;
    }
}

JavaScript:

var longestCommonPrefix = function(strs) {
    if (!strs || strs.length === 0) return "";
    let prefix = "";
    for (let i = 0; i < strs[0].length; i++) {
        let char = strs[0][i];
        let match = true;
        for (let j = 1; j < strs.length; j++) {
            if (i >= strs[j].length || strs[j][i] !== char) {
                match = false;
                break;
            }
        }
        if (match) prefix += char;
        else break;
    }
    return prefix;
};

C++:

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    string prefix = "";
    for (int i = 0; i < strs[0].length(); ++i) {
        char c = strs[0][i];
        bool match = true;
        for (int j = 1; j < strs.size(); ++j) {
            if (i >= strs[j].length() || strs[j][i] != c) {
                match = false;
                break;
            }
        }
        if (match) prefix += c;
        else break;
    }
    return prefix;
}

These examples all demonstrate the same efficient algorithm with minor syntactic differences. Remember to handle edge cases (empty input or single-string input) for robust code.