LeetCode #14. 最长公共前缀

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

方法一：横向扫描比较

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

$\LARGE LCP(S_{1}...S_{n}) =LCP(LCP(LCP(S_{1},S_{2}),S_{3}),...S_{n})$

先写比较函数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.longestCo