Longest Common Prefix Problem and Solution

1. Introduction

The "Longest Common Prefix" problem involves finding the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

2. Solution in C++

#include <iostream>
#include <vector>
using namespace std;

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;
}

// Example usage
int main() {
    vector<string> strs = {"flower", "flow", "flight"};
    cout << "Longest Common Prefix: " << longestCommonPrefix(strs) << endl;
    return 0;
}

Output:

Longest Common Prefix: fl

Explanation:

1. longestCommonPrefix in C++ iterates through the strings array.

2. It compares each string with the prefix (initialized to the first string).

3. The prefix is shortened one character at a time until it matches the start of each string.

4. Returns the longest common prefix.

3. Solution in Java

public class LongestCommonPrefix {
    public static 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;
    }

    // Example usage
    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println("Longest Common Prefix: " + longestCommonPrefix(strs));
    }
}

Output:

Longest Common Prefix: fl

Explanation:

1. Java's longestCommonPrefix method uses a similar approach as the C++ solution.

2. It iteratively shortens the prefix string until it matches the start of all strings in the array.

3. Returns the common prefix or an empty string if there is none.

4. Solution in Python

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

# Example usage
strs = ["flower", "flow", "flight"]
print("Longest Common Prefix:", longest_common_prefix(strs))

Output:

Longest Common Prefix: fl

Explanation:

1. Python's longest_common_prefix uses a similar approach.

2. Iteratively shortens the prefix until it matches the start of each string.

3. Continues this process for all strings and returns the longest common prefix.