LeetCode ＃14. 最长公共前缀

力扣 | # 14.最长公共前缀

方法一：横向扫描比较

思路：先将第一个字符串作为最长公共前缀，然后逐个和后面的字符串比较，记录新的最长公共前缀，直到全部遍历完成可得全部字符串的最长公共前缀。

先写比较函数LCP

取两个字符串中较小的并测量其长度。

利用循环比较两者中每一个元素的值，相等则指针index往后增加，一旦发现不相等则立刻跳出，最后返回前面相同的部分即为公共前缀。

    def LCP(self, str_1, str_2):
        n = len(min(str_1, str_2))
        index = 0
        for i in range(0, n):
            if str_1[i] == str_2[i]:
                index += 1
            else:
                break
        return str_1[:index]

然后是主函数longestCommonPrefix，先假定第一个字符串最为最长公共前缀，然后利用LCP函数和后面的字符串比较。将结果返回。

如果发现比较结果为空则立即跳出循环，不必再比较后面的字符串了，因为已经没有公共部分了。

if not max_com_prefix:
    break

全部代码如下

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        count = len(strs)
        max_com_prefix = strs[0]
        for i in range(1, count):
            max_com_prefix = self.LCP(max_com_prefix, strs[i])
            if not max_com_prefix:
                break

        return max_com_prefix

    def LCP(self, str_1, str_2):
        n = len(min(str_1, str_2))
        index = 0
        for i in range(0, n):
            if str_1[i] == str_2[i]:
                index += 1
            else:
                break
        return str_1[:index]

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower","flow","flight"]
    print(a.longestCommonPrefix(str_test01))

方法二：纵向扫描比较

思路：将所有数字中所有的字符串全部拿出来，依次比较每一个字符串中的字符。如果全部相等则比较下一字符，一旦发现有不相等的，立刻停止扫描。前面部分即为最大公共前缀。

先将数组中的第一个字符串的长度作为默认的最大前缀长度

length=len(strs[0])

 然后将计算数组中字符串是个数

count = len(strs)

重点循环部分

将第一个字符串的第i个字符作为比较的基准，比较每个字符串的第i个字符是否与它相同。

一旦发现第j个字符串的第i个字符与第一个字符串的第i个字符不相等，或者i刚好为第j个字符串的长度，则立即返回第一个字符串的前i个字符，即为最大公共前缀。

i在循环中不断增大，当i等于第j个字符串的长度时，说明该字符串已经遍历完成了，最大公共前缀不可能超过其中最小字符串的全部字符，所以应当立即返回第一个字符串的前i个字符，否则会有溢出错误。

for i in range(length):
    for j in range(1, count):
        if i == len(strs[j]) or strs[0][i] != strs[j][i]:
            return strs[0][:i]
return strs[0]

也可以写成如下样式

for i in range(length):
    c = strs[0][i]
    if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
        return strs[0][:i]
return strs[0]

any()函数参见

Python any() 函数 | 菜鸟教程

完整代码如下

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        length=len(strs[0])
        count = len(strs)
        for i in range(length):
            for j in range(1, count):
                if i==len(strs[j]) or strs[0][i] != strs[j][i]:
                    return strs[0][:i]
        return strs[0]

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower", "flow", "flight"]
    print(a.longestCommonPrefix(str_test01))

 另一种完整代码

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        length=len(strs[0])
        count = len(strs)
        for i in range(length):
            c = strs[0][i]
            if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
                return strs[0][:i]
        return strs[0]

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower", "flow", "flight"]
    print(a.longestCommonPrefix(str_test01))

利用zip函数

实现zip函数.

方法三：分治法

比较函数LCP满足结合律：

于是可以将一整段数字字符串分成两组比较，然后再将两者的结果比较得出最终结果。

而每一组又可以这样分成两组，不停的迭代。

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(start, end):
            if start == end:
                return strs[start]

            mid = (start + end) //2
            lcp_left = lcp(start, mid)
            lcp_right = lcp(mid+1, end)
            mid_length = min(len(lcp_left), len(lcp_right))
            for i in range(mid_length):
                if lcp_left[i] != lcp_right[i]:
                    return lcp_left[:i]
            return lcp_left[:mid_length]

        return "" if not strs else lcp(0, len(strs)-1)

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower", "flow", "flight"]
    print(a.longestCommonPrefix(str_test01))

方法四：二分查找法

先写判断函数，判断给定长度的部分字符串是否相同。

def is_common_fix(length):
    str0 = strs[0][:length]
    count = len(strs)
    for i in range (1, count):
        if strs[i][:length] != str0:
            return False
    return True

其中的for循环可以改写为三元表达式，利用all()函数迭代可以减少内存占用。

Python all() 函数 | 菜鸟教程

def is_common_fix(length):
    str0 = strs[0][:length]
    count = len(strs)
    return all( str0 == strs[i][:length] for i in range (1, count))

 找到整个数字字符串的最小字符长度

min_length = min(len(s) for s in strs)

然后循环二分并利用is_common_prefix()函数判断

low = 0
high = min_length
while low < high:
    mid = low + (high - low) // 2
    if is_common_prefix(mid):
        low = mid
    else:
        high = mid - 1

return strs[0][:low]

完整代码如下

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def is_common_prefix(length):
            str0 = strs[0][:length]
            count = len(strs)
            return all(strs[i][:length] == str0 for i in range (1, count))

        if not str:
            return ""

        min_length = min(len(s) for s in strs)
        low = 0
        high = min_length
        while low < high:
            mid = low + (high - low) // 2
            if is_common_prefix(mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower", "flow", "flight"]
    print(a.longestCommonPrefix(str_test01))

方法五：利用max(),min()函数

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        str0 = min(strs)
        str1 = max(strs)
        for i in range(len(str0)):
            if str0[i] != str1[i]:
                return str0[:i]
        return str0

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower", "flow", "flight"]
    print(a.longestCommonPrefix(str_test01))

方法六：利用zip()函数

zip()函数可以将数组中的元素分成一个一个的再对应打包。

Python zip() 函数 | 菜鸟教程

 *操作符可以将元组解压为列表

Python 元组 | 菜鸟教程

Python3 列表 | 菜鸟教程

strs = ["flower", "flow", "flight"]
x = zip(strs)
y = zip(*strs)

print(x)
print(y)
print(list(x))
print(list(y))

 结果如下

<zip object at 0x000002C0587005C8>
<zip object at 0x000002C058936188>
[('flower',), ('flow',), ('flight',)]
[('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]

set()函数可以将重复的元素合并为同一个

Python set() 函数 | 菜鸟教程

str1 = ["a", "a", "a"]
str2 = ["a", "a", "b"]
str3 = ["a", "b", "c"]

x = set(str1)
y = set(str2)
z = set(str3)

print(x)
print(y)
print(z)

结果如下

{'a'}
{'b', 'a'}
{'c', 'b', 'a'}

所以最后的完整代码如下

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ''
        for i in list(zip(*strs)):
            if len(set(i)) == 1:
                ans += i[0]
            else:
                break
        return ans

if __name__ == "__main__":
    a = Solution()
    str_test01 = ["flower", "flow", "flight"]
    print(a.longestCommonPrefix(str_test01))

扩展

自己实现zip函数

def my_zip(*args):
    min_len = min(len(item) for item in args)
    index = 0
    while index < min_len:
        new_item_list = [item[index] for item in args]
        index += 1
        yield tuple(new_item_list)

tuple()将列表转换为元组

Python Tuple(元组) tuple()方法 | 菜鸟教程

yield() 迭代器

*args：可以理解为只有一列的表格，长度不固定。

**kwargs：可以理解为字典，长度也不固定。