14.最长前缀子串Longest Common Prefix

发表于 更新于 分类于

定义

首先定义Longest Common Prefix(引用自Discuss@Vgn):

It seems that it is not to check between pair of strings but on all the strings in the array.

For example:
{“a”,“a”,“b”} should give “” as there is nothing common in all the 3 strings.

{“a”, “a”} should give “a” as a is longest common prefix in all the strings.

{“abca”, “abc”} as abc

{“ac”, “ac”, “a”, “a”} as a.

算法思想

  1. 取第一个字符串的第一个字符和后面的字符串的第一个对比，如果有一个不相同，或者字符串结束则返回
  2. 如果都相同，则向LCP中添加第一个字符
  3. 取第一个字符串的第二个字符…循环直到结束。

如果说上面这种是垂直扫描的思想，Solution中提到了另一种水平扫描的思想，先两两比较字符串的LCP，然后再和后面的字符串依次对比。

以上两种方法时间复杂度都是O(S)，空间复杂度O(1)。 其中S=m*n，n是string的个数，m是string的长度。

第三种想法是分治的思想，但是时间复杂度O(S), 需要O(m*log(n))的额外空间。

第四种想法是二分查找的思想，但是时间复杂度需要O(S*log(n))，空间O(1)。

关于分治和二分的时间复杂度，看到了一篇文章说的很好，http://blog.csdn.net/qilei2010/article/details/51345278

大意就是说二分法的复杂度一般是O(logN)，分治算法是O(N)，这是因为二分法每次丢弃不符合条件的一半，而分治算法只是将一个问题分成几个小问题，并没有降低问题的规模。

我的代码

string longestCommonPrefix(vector<string>& strs) {
    
string lcp="";
if (strs.size()!=0&&strs[0]!="")
{
    string s=strs[0];
    
    for (int j=0;j<s.length();j++)
    {
        char pre=strs[0][j];
        for(int i=1;i<strs.size();i++)
        {
            if (pre!=strs[i][j])
            {
                return lcp;
            }

        }
        lcp+=pre;

    }
}
return lcp;
    
}

注意判断输入为空和第一个字符串是空的情况。

看了网友的一些评论，发现了如下几个问题：

  1. 第一行处理异常情况，先返回

  2. 有网友指出lcp+=pre会多产生一个string，所以改用了index和substr

  3. 注意index++的时候要判断i是否遍历完了vector中所有的string

  4. 删除了一些不必要的定义比如s,pre

     if(strs.size()==0||strs[0]=="") return "";
 int index=0;
 for (int j=0;j<strs[0].length();j++)
 {
     int i=1;
     for(;i<strs.size()&&strs[i].size()>j;i++)
     {
         if (strs[0][j]!=strs[i][j])
         {
             return strs[0].substr(0,index);
         }

     }
     if(i==strs.size())index++;

 }
 return strs[0].substr(0,index);

看着好像简洁多了XD，但是没有什么卵用，依然是9ms。