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:

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.罗马数字包含以下七种字符: IVXLCDM


编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 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;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×