14. Longest Common Prefix

题目

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.

思路

我的思路是以第一个字符串为标准设为result ,依次寻找每个字符串的公共前缀,如果有不一样的就从result里把不一样的移除,剩下的result就是所求的公共前缀了。

然后就是看到别人的思路:从0开始依次遍历每一个字符串,如果是公共前缀就加到result里。

貌似我的比他快了一毫秒O(∩_∩)O~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//C++
string longestCommonPrefix(vector<string>& strs) {
if(strs.size() == 0) {
return "";
}
string result = strs[0];

for(string s:strs) {
if(s.size()==0) {
return "";
}
for(int i = 0;i<result.size() && i<s.size();i++) {
if(s[i] != result[i]) {
result.erase(i,result.size()-i);
break;
}
}
if(result.size()>s.size()) {
result.erase(s.size(),result.size()-s.size());
}
}
return result;
}

从0开始依次遍历每一个字符串,如果是公共前缀就加到result里。

1
2
3
4
5
6
7
8
9
//C++ 
string longestCommonPrefix(vector<string>& strs) {
string prefix = "";
for(int idx=0; strs.size()>0; prefix+=strs[0][idx], idx++)
for(int i=0; i<strs.size(); i++)
if(idx >= strs[i].size() ||(i > 0 && strs[i][idx] != strs[i-1][idx]))
return prefix;
return prefix;
}