Longest Common Prefix - LeetCode Solution in C++, Java, Python

1. Introduction

The "Longest Common Prefix" problem involves finding the longest prefix that is common across all strings in an array. The task is to write a function that returns this common prefix or an empty string if there is no common prefix among the strings.

2. Problem

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 "".

3. Solution in C++

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:

1. If the input array is empty, return an empty string.

2. Use the first string in the array as the initial prefix.

3. Iterate over the remaining strings, reducing the prefix until it matches the start of the current string.

4. If the prefix becomes empty, return an empty string.

5. After iterating through all strings, the remaining prefix is the longest common prefix.

4. Solution in Java

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

Explanation:

1. Check for an empty array and return an empty string if true.

2. Start with the first string in the array as the prefix.

3. Iterate through the array and shorten the prefix until the current string starts with it.

4. If at any point the prefix is empty, return an empty string.

5. The prefix after the iteration is the longest common prefix.

5. Solution in Python

def longestCommonPrefix(strs):
    if not strs:
        return ""
    shortest = min(strs, key=len)
    for i, ch in enumerate(shortest):
        for other in strs:
            if other[i] != ch:
                return shortest[:i]
    return shortest

Explanation:

1. Return an empty string if the input list is empty.

2. Find the shortest string in strs as a potential common prefix.

3. Iterate over each character of the shortest string.

4. Compare this character with the corresponding character in all other strings.

5. If a mismatch is found, return the substring of the shortest string up to the current index.

6. If no mismatches are found, return the entire shortest string as the common prefix.