力扣(LeetCode)14. 最长公共前缀(C++)

模拟

取出 $strs$ 的第一个字符串 $strs[0]$ ， 遍历$strs[0]$ ， 依次比较所有串的当前位置的字符，是否和 $strs[0]$ 的当前字符相同。

代码展示

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs[0].size();
        string ans;
        if(strs.empty()) return ans;
        int i = 0;
        while(i<n){
            for(auto &x:strs){
                if(x.size()<=i || x[i]!=strs[0][i]) return ans;
            }
            ans += strs[0][i];
            i++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度 $O(n\times {\sum }_{i=0}^{n-1}{m}_i)$ ， $n$ 是 $strs$ 的长度， $m_i$ 是 $strs[i]$ 的长度。遍历所有串的所有字符，时间复杂度 $O(n\times {\sum }_{i=0}^{n-1}{m}_i)$。

空间复杂度 $O(1)$ ， 除答案所使用的空间外，没有使用额外的线性空间 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC