题目简介：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
1
2
| 输入: ["flower","flow","flight"]
输出: "fl"
|
示例 2:
1
2
3
| 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
|
说明:
所有输入只包含小写字母 a-z 。
思路：
首先将数组以字符串长度进行排序，因为最长的公共前缀最多也就是数组中最短的字符串。
然后便是遍历数组中其他字符串，找出与最短的那个字符串的最长公共前缀，如果一旦有不一样的字符出现，则直接break跳出循环，不必再继续向下遍历了。
双重循环本来以为会超时的，没想到才4ms，还挺快的…
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| bool cmp(string& s1, string& s2){
return s1.length() < s2.length();
}
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty())
return "";
sort(strs.begin(), strs.end(), cmp);
string res;
for(int i = 0; i < strs[0].length(); i++){
int flag = 0;
for(int j = 1; j < strs.size(); j++){
if(strs[j][i] != strs[0][i]){
flag = 1;
break;
}
}
if(flag == 0)
res += strs[0][i];
else
break;
}
return res;
}
};
|
