LeetCode

Appearance

14. 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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

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

 

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters if it is non-empty.
Related Topics
  • 字典树
  • 数组
  • 字符串

  • 👍 3425
  • 👎 0

    • 解法一 ​

    枚举比较全部单词

    python
    class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ""
        max_len = len(strs[0])
        for i in range(0, max_len):
            first = strs[0][i]
            for j in range(1, len(strs)):
                word = strs[j]
                if i >= len(word) or first != word[i]:
                    return ans
            else:
                ans += first


        return ans

    复杂度分析 ​

    N = len(strs) M = avg of strs[i]

    • 时间复杂度 O(N * N * M)
    • 空间复杂度 O(1)

    解法二 ​

    对数组先进行排序，此时只需比较第一个和最后一个即可

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort()

        first = strs[0]
        last = strs[-1]

        i = 0

        while i < len(first) and i < len(last) and first[i] == last[i]:
            i += 1

        return first[:i]

# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    N = len(strs) M = avg of strs[i]

    • 时间复杂度 O(Nlog N * M)
    • 空间复杂度 O(N) - 因为 python sort的实现需要额外的空间机制导致 纯算法机制为 O(1)