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:
1
2
| Input: ["flower","flow","flight"]
Output: "fl"
|
Example 2:
1
2
3
| 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.罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
1
2
| 输入: ["flower","flow","flight"]
输出: "fl"
|
示例 2:
1
2
3
| 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
|
说明:
所有输入只包含小写字母 a-z 。
想法
从第一个字符串开始循环比对，如果字符不相同则缩短前缀长度，最终输出即可。
解
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
38
| #include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string> &strs)
{
if (strs.size() <= 0) {
return "";
}
else {
string prefix = strs[0];
int index = prefix.size();
for (string &s : strs) {
for (int i = 0; i < min(index, static_cast<int>(s.size())); i++) {
if (prefix[i] != s[i]) {
index = i;
break;
}
}
index = min(index, static_cast<int>(s.size()));
}
return prefix.substr(0, index);
}
}
};
int main(void)
{
Solution s;
vector<string> strs = {"aa", "a"};
cout << s.longestCommonPrefix(strs) << endl;
return 0;
}
|
