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.
最长公共前缀
看到前缀 我就想到了tries 树， 但是一看这题是easy........
我们假设 有 N个字符串 ， 平均长度为 M
我们暴力比较 第 i (0..m) 位， 复杂度为 N*M
其实用 tries树 时间复杂度反而高，而且还要开空间。。。
所以这题就暴力比较啦。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty())
return "";
// 特殊处理 strs 只有一个字符串 的情况
if(strs.size()==1){
return strs[0];
}
int ptr = 0;
// 循环比较 每个字符串的 第 i 位
while(true){
// 循环 比较！ 如果出现 1. 前后不一致 或者 2. 某一字符串越界
// 这个循环 不能处理 strs.size() <=1 的情况 所以上面要特殊处理
for(int i =1; i <strs.size();++i){
if( ptr == strs[i].size() || strs[i][ptr] != strs[i-1][ptr]){
//结束循环 打印结果
return strs[0].substr(0,ptr);
}
}
ptr++;
}
}
};
image.png
