题目地址:https://leetcode-cn.com/problems/longest-common-prefix/
题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
题目示例
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
解题思路
思路1:我们对字符串数组strs,依次遍历其中的每个字符串(单词),对于每个遍历到的字符串,更新最长公共前缀,当遍历完所有的字符串以后,即可得到字符串数组中的最长公共前缀prefix。时间复杂度O(mn),其中m为字符串数组中的字符串的平均长度,n为字符串数组的长度,空间复杂度O(1)。
思路2:国际站一位老哥代码,个人感觉非常容易理解。思路主要是先对字符串数组进行排序,然后选择排好序之后的字符串数组中的第一个和最后一个字符串,最后比较两个字符串从下标0开始有多少个公共字符。
程序源码
思路1
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()) return ""; //字符串数组没有字符串
string prefix = strs[0];
for(int i = 1; i < strs.size(); i++)
{
prefix = longestCommonPrefix(prefix, strs[i]);
if(prefix.empty())
{
break;
}
}
return prefix;
}
string longestCommonPrefix(string& s1, string& s2)
{
int word_len = min(s1.size(), s2.size());
int index = 0;
while(index < word_len && s1[index] == s2[index])
{
index++;
}
return s1.substr(0, index);
}
};
精简代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string prefix = strs.size()? strs[0] : "";
for(auto str : strs)
{
while(str.substr(0, prefix.size()) != prefix)
{
prefix = prefix.substr(0, prefix.size() - 1);
if(prefix == "") return prefix;
}
}
return prefix;
}
};
思路2
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(!strs.size()) return "";
string prefix = "";
sort(begin(strs), end(strs));
string sa = strs[0];
string sb = strs[strs.size() - 1];
for(int i = 0; i < sa.size(); ++i)
{
if(sa[i] == sb[i])
{
prefix += sa[i];
}
else
break;
}
return prefix;
}
};
原文链接: https://www.cnblogs.com/wzw0625/p/13575714.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/202063
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!