Longest Common Prefix

14. Longest Common Prefix

分析

首先看所有字符串第一个字符是否一样，一样则公共字符串长度至少为1，否则公共字符串为空。再看第二个字符是否一样，这样一直遍历下去… 最坏情况就是把所有字符串的每个字符枚举一遍，时间复杂度小于等于所有字符串之和。

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if (strs.empty()) return res;

        for (int i = 0;; i ++ ) {
            if (i >= strs[0].size()) return res;
            char c = strs[0][i];
            for (auto& str: strs)
                if (i >= str.size() || str[i] != c)
                    return res;
            res += c;    
        }
        return res;
    }
};