Longest Common Prefix

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

这是一道字符串的简单题.思路也非常简单,基本都是brute force的解法.具体解法分为:按列扫和按行扫两种.

按列扫,是每次从第一个字符串中取一个出来,比较其余所有字符串响应位置字符是否相同,不相同则退出.返回第一个字符串的子串.

按行扫,是每个拿一个字符串去和第一个字符串比较,获得当前相同子串的长度.之后每个字符串跟其相比时,都不超过当前这个子串的长度.

两种解法的时间复杂度都是O(n1+n2+n3+n4...),空间复杂度为O(1).

使用python解这种题目时有非常多的trick.合理使用可以提速很多.

按行扫不使用trick版本,运行时间60ms.比较慢.

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
     
        for j in range(len(strs[0])):
           for i in range(1,len(strs)):
                if j >= len(strs[i]) or strs[i][j] !=strs[0][j]:
                    return strs[0][:j]
        return strs[0]
           

按行扫使用trick版本,运行时间48ms,使用zip来实现.zip实际是将行字符串做了按列的一个排列,且处理到最短的序列长度.但是引入了O(n1+n2+n3+..)的空间复杂度,所以实际是以空间换时间.数据量大时不建议用.

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        sz ,ret = zip(*strs),""
        for c in sz:
            if len(set(c))>1:
               break
            ret += c[0]
        return ret

按列扫方法,我没有具体实现,贴上别人实现的C++版本:

class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
    if (strs.empty()) return "";
    int right_most = strs[0].size() - 1;
    for (size_t i = 1; i < strs.size(); i++)
        for (int j = 0; j <= right_most; j++)
            if (strs[i][j] != strs[0][j]) // 不会越界，请参考 string::[] 的文档
                right_most = j - 1;
    return strs[0].substr(0, right_most + 1);
  }
};