Skip to content

014 longest common prefix

14. Longest Common Prefix

题目: https://leetcode.com/problems/longest-common-prefix/

难度:

Easy

思路：

解法1:

以一个小例子来解释，strs=['laa', 'lab', 'lac'], 如果存在LCP的话它肯定就在第一个字符串strs[0]中，并且LCP的长度肯定不会大于strs[0]的长度 - 依次假设LCP长度为0到len(strs[0]),在每一轮循环中:   - 1. 只要strs中存在比当前长度i更短的string，立刻返回上一轮LCP，即strs[0][:i] 2. 只要strs中存在当前index字符与LCP该index不相同的字符串，立刻返回上一轮LCP，即strs[0][:i] - 如果一直没返回，说明strs[0]本身就是LCP，返回它

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

解法2:

  • dp[i]代表前i+1个字符串的最大前缀串，
  • 如果第i+2个字符串不以dp[i]为前缀，就去掉dp[i]的最后一个字符再试一次
  • 都去完了那么dp[i+1]肯定就是空串了，也就等于这时候的dp[i]，因为dp[i]的每个字符已经被去完了
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        dp = [strs[0]]*len(strs)
        for i in range(1,len(strs)):
            while not strs[i].startswith(dp[i-1]):
                dp[i-1] = dp[i-1][:-1]
            dp[i] = dp[i-1]
        return dp[-1]

python无敌啊！！！有没有天理啊，手动滑稽😏😏😏😏！一行解法：

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        return os.path.commonprefix(strs)
回到顶部