LeetCode 14. Longest Common Prefix(字符串)
LeetCode 14 Longest Common Prefix字符串
问题描述解题思路参考代码
By ScarbScarb’s Blog
Tags: - String
问题描述
Write a function to find the longest common prefix string amongst an array of strings.
解题思路
题意是要找出一个字符串数组中最长的前缀公共子串。 我先将字符串排序，最短的放最前面。然后遍历所有字符串，为最短字符串的每一位都分别与其他字符串进行比较。 如果都相同，那最大长度加以，否则跳出循环。
参考代码
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
string longestCommonPrefix(
vector<string>& strs) {
if (strs.size() <=
0)
return "";
int max_len =
0;
bool flag;
sort(strs.begin(), strs.end());
for (
int i =
0; i < strs[
0].length(); ++i)
{
flag =
true;
char ch = strs[
0][i];
for (
auto str : strs)
{
if (str[i] != ch)
{
flag =
false;
break;
}
}
if (!flag)
break;
++max_len;
}
return strs[
0].substr(
0, max_len);
}
};
int main()
{
vector<string> strs = {
"12345",
"1234",
"123",
"12354" };
auto sl =
new Solution();
cout << sl->longestCommonPrefix(strs) << endl;
system(
"pause");
return 0;
}
