0014._longest_common_prefix.md

14. Longest Common Prefix

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/longest-common-prefix/

内容描述

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 "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

解题方案

思路 1 ******- 时间复杂度: O(N * len(strs(0)) - 空间复杂度: O(N)

• dp[i]代表前i+1个字符串的最大前缀串，
• 如果第i+2个字符串不以dp[i]为前缀，就去掉dp[i]的最后一个字符再试一次
• 都去完了那么dp[i+1]肯定就是空串了，也就等于这时候的dp[i]，因为dp[i]的每个字符已经被去完了

beats 96.61%

class Solution:
    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]

思路 2 ******- 时间复杂度: O(N * len(strs(0)) - 空间复杂度: O(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]

思路 3 ******- 时间复杂度: O(N * len(strs(0)) - 空间复杂度: O(1)

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

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