14. 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: ["flower","flow","flight"]
Output: "fl"

Example 2:

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

Note:

All given inputs are in lowercase letters a-z.

string longestCommonPrefix(vector<string>& strs) { // time: O(m * n); space: O(m), m: vector size, n: first string length
    if (strs.empty())  return "";
    for (int idx = 0; idx < strs[0].length(); ++idx) {
        char ch = strs[0][idx];
        for (int i = 1; i < strs.size(); ++i) {
            if (idx >= strs[i].length() || strs[i][idx] != ch) {
                return strs[0].substr(0, idx);
            }
        }
    }
    return strs[0];
}

string longestCommonPrefix(vector<string>& strs) { // time: O(m * n); space: O(m), m: vector size, n: first string length
    string res;
    if (strs.empty()) return "";
    for (int i = 0; i < strs[0].length(); ++i) {
        for (int j = 1; j < strs.size(); ++j) {
            if (strs[0][i] != strs[j][i]) return res;
        }
        res += strs[0][i];
    }
    return strs[0];
}