14. 最长公共前缀
代码仓库地址： https://github.com/slience-me/Leetcode
个人博客 ：https://slienceme.xyz
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
方案1：暴力解 历史最差代码没有之一
第一种纯暴力解，很多不合理的地方，考场上只是为了拿基础分，就是结果导向性解题方式
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs[0] == ""){
return "";
}
int maxsize = -1;
for (const auto &item: strs){
maxsize = max(maxsize, static_cast<int>(item.size()));
}
string res;
for (int i = 0; i < maxsize; ++i) {
char temp = strs[0][i];
string tmp ;
for (int j = 0; j < strs.size(); ++j) {
if (temp == strs[j][i]){
cout<<"temp: "<<temp<<" strs[j][i]: "<<strs[j][i]<<" i: "<<i<<" j: "<<j<<endl;
tmp = strs[j][i];
} else {
tmp = "";
goto outerLoop; // 跳到外层循环的标签位置
}
}
res.append(tmp);
}
outerLoop:
return res;
}
};
执行用时分布 48ms 击败6.69%使用 C++ 的用户
消耗内存分布9.37MB 击败15.46%使用 C++ 的用户
方案2
初次优化，这种方案比上一种更加合理，去除掉了很多冗余的代码 i >= s.length()关键条件 s[i] != tmp
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
for (int i = 0; i < 200; ++i) {
if (i > strs[0].length())
return res; //处理空情况
char tmp = strs[0][i];
for (const auto &s: strs) {
if (i >= s.length())
return res;// 超出了，则说明当前字符串长度不够 flower flow i=5 >= 4
if (s[i] != tmp)
return res;
}
res += tmp;
}
return res;
}
};
执行用时分布 0ms 击败100%使用 C++ 的用户
消耗内存分布 9.04MB 击败63.16%使用 C++ 的用户
方案3
最后的优化，没有太大的提升
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ans = "";
// 用第一个单词的字符一次遍历全部字符串
for (int i = 0; i < strs[0].size(); ++i) {
bool flag = true;
for (int j = 1; j < strs.size(); ++j) {
if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {
flag = false; // 合二为一
break; // 退出里循环
}
}
if (flag) {
ans += strs[0][i];
} else {
break; // 退出外循环
}
}
return ans;
}
};
执行用时分布 4ms 击败%使用 C++ 的用户
消耗内存分布 9.12MB 击败46.03%使用 C++ 的用户
文档信息
- 本文作者：slience_me
- 本文链接：https://slienceme.xyz/2023/11/22/Leetcode_14/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）