[LeetCode 题解]: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

题解：寻找一组字符串的最长公共前缀。

最简单的方法，用一个字符串记录当前最长的公共前缀，然后依次比较。时间复杂度： O(N).

 class Solution {

 public:

     string getPrefix(string a,string b)   // 辅助函数用于获取两个字符串的公共前缀

     {

         string ans;

         for(int i=;i<a.size() && i<b.size();i++)

         {

             if(a[i]==b[i])  ans+=a[i];

             else break;

         }

         return ans;

     }

     string longestCommonPrefix(vector<string> &strs) {

         string a;

         int len = strs.size();

         if(!len) return a;

         a = strs[];

         for(int i=;i<len;i++) a= getPrefix(a,strs[i]);

         return a;

     }

 };

高效的方法，采用分治法，先分块，后合并比较，时间复杂度O(logN)。

 class Solution {

 public:

     string getPrefix(string a,string b)   //辅助函数，用于获取两个字符串的公共前缀

     {

         string ans;

         for(int i=;i<a.size() && i<b.size();i++)

         {

             if(a[i]==b[i])  ans+=a[i];

             else break;

         }

         return ans;

     }

     string commonPrefix(int left,int right, vector<string> &strs)   //分治法寻找commonPrefix

     {

         if(left>=right) return strs[left];

         if(left+==right) return getPrefix(strs[left],strs[right]);

         int middle = (right+left)>>;

         return getPrefix(commonPrefix(left,middle,strs),commonPrefix(middle+,right,strs));

     }

     string longestCommonPrefix(vector<string> &strs) {

         int i=,len=strs.size();

         string a;

         if(!len) return a;

         return commonPrefix(,len-,strs);

     }

 };

转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！

巴特西

[LeetCode 题解]: Longest Common Prefix

最新文章

热门文章