首页 > 代码库 > LeetCode: Longest Common Prefix 题解
LeetCode: Longest Common Prefix 题解
Write a function to find the longest common prefix string amongst an array of strings.
题解： 寻找一组字符串的最长公共前缀。
最简单的方法，用一个字符串记录当前最长的公共前缀，然后依次比较。时间复杂度： O(N).
1 class Solution { 2 public: 3 string getPrefix(string a,string b) // 辅助函数用于获取两个字符串的公共前缀 4 { 5 string ans; 6 for(int i=0;i<a.size() && i<b.size();i++) 7 { 8 if(a[i]==b[i]) ans+=a[i]; 9 else break;10 }11 return ans;12 }13 string longestCommonPrefix(vector<string> &strs) {14 string a;15 int len = strs.size();16 if(!len) return a;17 a = strs[0];18 for(int i=1;i<len;i++) a= getPrefix(a,strs[i]);19 return a;20 }21 };
高效的方法，采用分治法，先分块，后合并比较，时间复杂度O(logN)。
1 class Solution { 2 public: 3 string getPrefix(string a,string b) //辅助函数，用于获取两个字符串的公共前缀 4 { 5 string ans; 6 for(int i=0;i<a.size() && i<b.size();i++) 7 { 8 if(a[i]==b[i]) ans+=a[i]; 9 else break;10 }11 return ans;12 }13 string commonPrefix(int left,int right, vector<string> &strs) //分治法寻找commonPrefix14 {15 if(left>=right) return strs[left];16 if(left+1==right) return getPrefix(strs[left],strs[right]);17 int middle = (right+left)>>1;18 return getPrefix(commonPrefix(left,middle,strs),commonPrefix(middle+1,right,strs));19 }20 string longestCommonPrefix(vector<string> &strs) {21 int i=0,len=strs.size();22 string a;23 if(!len) return a;24 return commonPrefix(0,len-1,strs);25 }26 };
转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。