Determine the longest common prefix among a collection of strings. If no common prefix exists, return an emppty string "".

Examples:

Example 1:

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

Example 2:

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

Constraints:

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

Solution 1: Character-by-Character Comparison

Initialize by chceking if the input vector is empty. If it is, return an empty string. Use the first string as the reference for comparision. Iterate through each character position of this reference string. For each position, compare the character with the character at the same index in every other string. If a mismatch is found or a string is shorter than the current index, return the substring of the reference string up to that point.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strings) {
        if (strings.empty()) {
            return "";
        }
        string base = strings[0];
        int n = strings.size();
        int refLength = base.size();

        for (int pos = 0; pos < refLength; ++pos) {
            char currentChar = base[pos];
            for (int strIdx = 1; strIdx < n; ++strIdx) {
                if (pos >= strings[strIdx].size() || strings[strIdx][pos] != currentChar) {
                    return base.substr(0, pos);
                }
            }
        }
        return base;
    }
};

Solution 2: Prefix Reduction Approach

Start by assuming the entire first string is the common prefix. Iterate through the remaining strings. For each string, repeatedly shorten the candidate prefix from the end until it is a prefix of the current string. If the candidate becomes empty, there is no common prefix.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strings) {
        if (strings.empty()) return "";
        string candidate = strings[0];
        
        for (int i = 1; i < strings.size(); ++i) {
            while (strings[i].find(candidate) != 0) {
                candidate.pop_back(); // Shorten the prefix by one character
                if (candidate.empty()) {
                    return "";
                }
            }
        }
        return candidate;
    }
};