leetcode_14

发表于   |   分类于

Longest Common Prefix

题目戳这

题意

给一个字符串数组strs,求其中所有字符串的最长公共前缀

解法

这道题目题目本身提供了四种解法。

  1. 先求出第一个字符串和第二个字符串的最长公共前缀str,然后将str逐一与后面的字符串进行比较，在比较的过程中不断修整(减小)str的长度，最终比较出最长公共前缀。这个方法称为 水平扫描法。时间复杂度为O(S),S为所有字符串的长度总和
  2. 按列进行比较，看到哪一列无法匹配了，那么我们就停止往后匹配，然后前一列能够匹配到的就是最长的匹配前缀。这个方法称为 垂直扫描法。时间复杂度为O(n*minLen)，n为字符串的数量，minLen为最短的字符串长度。
  3. 这个方法是将字符串数组进行递归二分，左一半右一半，递归边界为左右指针指向同一个字符串，然后将一左一右进行匹配，得到的最长公共前缀继续与其他字符串进行匹配，直到全部都比较完。
  4. 这与第3个方法有一些相似，然而这二分的是字符串的长度，每次二分出的区域结果用来对所有字符串进行截取比较，看是否是一个最长公共前缀的子串，如果是的话，那么就将二分区域变大，继续寻找，否则将该区间变短。

代码

解法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):     # horizontal scanning
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        slen = len(strs)
        if slen == 0:
            return ""
        if slen == 1:
            return strs[0]
        ls = ""
        ss = len(strs[0]) if len(strs[0]) < len(strs[1]) else len(strs[1])
        for i in range(ss+1):
            if strs[0][0:i] == strs[1][0:i]:
                ls = strs[0][0:i]
        if ls == "":
            return ls
        for i in range(2, slen):
            ss = len(strs[i]) if len(strs[i]) < len(ls) else len(ls)
            tmp = ""
            for j in range(ss+1):
                if strs[i][0:j] == ls[0:j]:
                    tmp = ls[0:j]
            ls = tmp
        return ls

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object): # vertical scanning
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        if len(strs) == 1:
            return strs[0]
        lenarray = [len(str) for str in strs]
        minlen = min(lenarray)
        res = ""
        for j in range(minlen):
            tmp = strs[0][j]
            flag = 1
            for i in range(1, len(strs)):
                if strs[i][j] != tmp:
                    flag = 0
                    break
            if flag:
                res += tmp
            else:
                break
        return res

解法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):   # divide and conquer
    def longestCommonPrefix1(self, strs, lt, rt):
        if lt == rt:
            return strs[lt]
        else:
            mid = (lt+rt)//2
            lstr = self.longestCommonPrefix1(strs, lt, mid)
            rstr = self.longestCommonPrefix1(strs, mid+1, rt)
            return self.findlcp(lstr, rstr)
        pass
    def findlcp(self, str1, str2):
        slen = min(len(str1), len(str2))
        for i in range(slen):
            if str1[i] != str2[i]:
                return str1[0:i]
        return str1[0:slen]
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        if len(strs) == 1:
            return strs[0]
        return self.longestCommonPrefix1(strs, 0, len(strs)-1)

解法4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):    # binary search
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        if len(strs) == 1:
            return strs[0]
        lenarray = [len(str) for str in strs]
        minlen = min(lenarray)
        if minlen == 0:
            return ""
        l = 0
        r = minlen
        while l<=r:
            mid = (l+r)//2
            if self.lcp(strs, mid):
                l = mid+1
            else:
                r = mid-1
        return strs[0][0:(l+r)//2]
    def lcp(self, strs, len1):
        str = strs[0][0:len1]
        for i in range(1,len(strs)):
            if strs[i][0:len1] != str:
                return False
        return True