首页 > 代码库 > [LeetCode] Longest Common Prefix 字符串公有前序
[LeetCode] Longest Common Prefix 字符串公有前序
Write a function to find the longest common prefix string amongst an array of strings.
Hide Tags
String 这是一道很简单的题目,判断输入的多个字符串的公有前序,简单的逻辑遍历查找就好。
算法流程:
- 判断输入的字符串数量,小于2时候做出相应返回。
- 获取最短字符串的长度。
- 设定标记flag,控制跳出循环,与长度返回的长度len。
- 在最短字符串长度的范围内循环。
- 循环中每次遍历全部字符串len 位的字符。
- 遇到不同设置flag 跳出循环,如果全部都相同len+1 进入下次循环。
- 返回长度。
其实可以简单点不求最短字符串长度,将这一步放入到判断是否相同时候。
1 #include <iostream> 2 #include <vector> 3 #include <string> 4 using namespace std; 5 6 class Solution { 7 public: 8 string longestCommonPrefix(vector<string> &strs) { 9 int nvec = strs.size();10 if(nvec<1) return "";11 if(nvec<2) return strs[0];12 int nmin = strs[0].length(),len=0;13 bool flag = true;14 for(int i =1;i<nvec;i++){15 if(nmin>strs[i].length()) nmin = strs[i].length();16 }17 while(len<nmin){18 for(int i=1;i<nvec&&flag;i++){19 if(strs[i][len]==strs[0][len]) continue;20 flag = false;21 }22 if(!flag) break;23 len++;24 }25 return strs[0].substr(0,len);26 }27 };28 29 int main()30 {31 vector<string> strs={"289","25324","22434","232","234"};32 Solution sol;33 cout<<sol.longestCommonPrefix(strs)<<endl;34 return 0;35 }
[LeetCode] Longest Common Prefix 字符串公有前序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。