首页 > 代码库 > [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
 
    这是一道很简单的题目,判断输入的多个字符串的公有前序,简单的逻辑遍历查找就好。
算法流程:
  1. 判断输入的字符串数量,小于2时候做出相应返回。
  2. 获取最短字符串的长度。
  3. 设定标记flag,控制跳出循环,与长度返回的长度len。
  4. 在最短字符串长度的范围内循环。
  5. 循环中每次遍历全部字符串len 位的字符。
  6. 遇到不同设置flag 跳出循环,如果全部都相同len+1 进入下次循环。
  7. 返回长度。

其实可以简单点不求最短字符串长度,将这一步放入到判断是否相同时候。

 

 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 }
View Code

 

[LeetCode] Longest Common Prefix 字符串公有前序