LeetCode 14 Longest Common Prefix (Python)

Posted by 小明MaxMing on November 1, 2024

题目

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

If there is no common prefix, return an empty string “”.

解题思路

方法1,前两个字符串求最长公共前缀,结果和下一个字符串求,直到结束

方法2,对所有字符串排序,结果为第一和最后一个字符串的最长公共前缀

代码

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def get_common_prefix(s1, s2):
            if len(s1) > len(s2):
                s1, s2 = s2, s1
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    return s1[:i]
            return s1

        if len(strs) == 0:
            return ""
        if len(strs) == 1:
            return strs[0]
        res = get_common_prefix(strs[0], strs[1])
        for s in strs[2:]:
            res = get_common_prefix(res, s)
        return res
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def get_common_prefix(s1, s2):
            if len(s1) > len(s2):
                s1, s2 = s2, s1
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    return s1[:i]
            return s1

        strs = sorted(strs)
        return get_common_prefix(strs[0], strs[-1])

视频讲解 YouTube<--欢迎点击订阅

视频讲解 bilibili<--欢迎点击订阅