Longest Common Prefix
最后更新于:2022-04-01 22:56:37
**一. 题目描述**
Write a function to find the longest common prefix string amongst an array of strings.
**二. 题目分析**
题目的大意是,给定一组字符串,找出所有字符串的最长公共前缀。
对比两个字符串的最长公共前缀,其前缀的长度肯定不会超过两个字符串中较短的长度,设最短的字符串长度为`n`,那么只要比较这两个字符串的前`n`个字符即可。
使用变量`prefix`保存两个字符串的最长公共前缀,再将`prefix`作为一个新的字符串与数组中的下一个字符串比较,以此类推。
一个特殊情况是,若数组中的某个字符串长度为`0`,或者求得的当前最长公共前缀的长度为`0`,就直接返回空字符串。
**三. 示例代码**
~~~
#include
#include
#include
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector &strs)
{
if (strs.size() == 0)
return "";
string prefix = strs[0];
for (int i = 1; i < strs.size(); ++i)
{
if (prefix.length() == 0 || strs[i].length() == 0)
return "";
int len = prefix.length() < strs[i].length() ? prefix.length() : strs[i].length();
int j;
for (j = 0; j < len; ++j)
{
if (prefix[j] != strs[i][j])
break;
}
prefix = prefix.substr(0,j);
}
return prefix;
}
};
~~~
![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5efdf922.jpg)
**四. 小结**
该题思路不难,而且还有几种相似的解决思路,在实现时需要做到尽量减少比较字符的操作次数。
';