14. Longest Common Prefix

问题

Write a function to find the longest common prefix string amongst an array of strings.

例子

["abdc", "abfg", "abc"]
"ab"

分析

同步遍历数组中的所有字符串，直到所有字符串的当前字符不同或者有字符串遍历结束，返回之前遍历过的所有字符。

要点

简单的遍历字符串即可。

时间复杂度

O(n)，n是所有字符串长度的最小值。

空间复杂度

O(1)

代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        
        string res;
        for (int i = 0; ; i++) {
            char c = '\0';
            for (const string &str : strs) {
                if (str.size() <= i) return res;
                if (c == '\0') c = str[i];
                else if (c != str[i]) return res;
            }
            res += c;
        }
        return res;
    }
};