LeetCode 14 最长公共前缀(c++)
2022/2/10 1:20:00
本文主要是介绍LeetCode 14 最长公共前缀(c++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 题目要求
- 解法
题目要求
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。- 示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl” - 示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:""
解释:输入不存在公共前缀。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法
可以实现一个方法在两个字符串间寻找最长公共前缀,即按位比较,直到不一致时跳出,即可得到最长公共前缀。然后用这个得到的串再和数组内其他的字符串求最长公共前缀,直到遍历数组结束。
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) { return ""; } string res = strs[0]; for (int i = 1; i < strs.size(); i++) { res = getCommonPrefix(res, strs[i]); } return res; } string getCommonPrefix(string str00, string str01) { string res = ""; int len00 = str00.size(); int len01 = str01.size(); int len = len00 <= len01 ? len00 : len01; for (int i = 0; i < len; i++) { if (str00[i] == str01[i]) { res += str00[i]; } else { break; } } return res; } };
复杂度分析
时间复杂度:遍历数组及字符串
O
(
m
n
)
O(mn)
O(mn),m表示单个字符串长度,n表示数组大小
空间复杂度:
O
(
m
)
O(m)
O(m),借助了临时字符串作存储
这篇关于LeetCode 14 最长公共前缀(c++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升