题目描述
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。
说明:所有输入只包含小写字母 a-z 。
示例
示例1:
输入: ["flower","flow","flight"]
输出: "fl"
示例2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
题目解析
我的思路是,首先对所有的字符串进行排序,因为存入了vector,所以直接使用sort排序即可。然后,寻找第一个字符串和最后一个字符串的最大公共前缀,就是整个数组的公共前缀。
当然,要考虑一些特殊情况:
1. 数组中是一个或一个以上空字符串。
2. 数组为空。
具体解决方法在下面的代码已经体现。
代码实现
string longestCommonPrefix(vector<string>& strs) {
string res;
int strslen = strs.size();
if (strslen < 1)
return res;
else if (strslen == 1)
return strs[0];
sort(strs.begin(), strs.end());
int i = 0;
for (int i = 0; i < strslen; i++)
{
if (strs[i].size() == 0)
return res;
}
int llen = strs[0].size();
int rlen = strs[strslen - 1].size();
int mlen = min(llen, rlen);//保证比较最小的长度
while (strs[0][i] == strs[strslen - 1][i])
{
res += strs[0][i];
if (i < mlen)//如果已经达到最小长度就退出
++i;
else
break;
}
return res;
}
文章评论