LeetCode 14 最长公共前缀
2021/5/8 18:57:51
本文主要是介绍LeetCode 14 最长公共前缀,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
14. 最长公共前缀
难度简单编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
输入:strs = ["flower","flow","flight"] 输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"] 输出:"" 解释:输入不存在公共前缀。
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (!strs.size()) { return ""; } string prefix = strs[0]; int count = strs.size(); for (int i = 1; i < count; ++i) { prefix = longestCommonPrefix(prefix, strs[i]); if (!prefix.size()) { break; } } return prefix; } string longestCommonPrefix(const string& str1, const string& str2) { int length = min(str1.size(), str2.size()); int index = 0; while (index < length && str1[index] == str2[index]) { ++index; } return str1.substr(0, index); } };
o(m*n)
其中 m是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。
其实就是暴力求解
复杂度o(m*n) m为最短字符串的长度 n为字符串的个数
长度为1 遍历一次
长度为2 遍历一次
长度为3 遍历一次
。。。。。
长度为最短字符串长度遍历一次
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if(!strs.size()){ return ""; } int minL = getMinL(strs); string pre = ""; bool flag = false; for(int i =0; i< minL; i++){ for(int j = 0; j < strs.size(); j++){ if(strs[0].substr(0,i+1) != strs[j].substr(0,i+1)){ flag = true; break; } } if (flag){ break; } else{ pre = strs[0].substr(0,i+1); } } return pre; } int getMinL(vector<string>& strs){ int minL = pow(2,31) -1; for (int i =0; i<strs.size(); i++){ if (minL > strs[i].length()){ minL = strs[i].length(); } } return minL; } };
s='abc'
s.substr(0,0) -> ''
s.substr(0,1) -> 'a'
这篇关于LeetCode 14 最长公共前缀的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享