14_最长公共前缀

类型：字符串

• 14. 最长公共前缀 💚

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

  ❓ 查找字符串数组的公共前缀。

  输入：strs = [“flower”,“flow”,“flight”] 输出：“fl”

  💡 横向扫描

  class Solution:
      def longestCommonPrefix(self, strs: List[str]) -> str:
          if not strs:
              return ""
  
          prefix, count = strs[0], len(strs)
          for i in range(1, count):
              prefix = self.lcp(prefix, strs[i])
              if not prefix:
                  break
  
          return prefix
  
      def lcp(self, str1, str2):
          length, index = min(len(str1), len(str2)), 0
          while index < length and str1[index] == str2[index]:
              index += 1
          return str1[:index]

  时间复杂度：O(mn)，m 指字符串平均长度，n 指字符串数量。空间复杂度：O(1)

  💡 纵向扫描

  class Solution:
      def longestCommonPrefix(self, strs: List[str]) -> str:
          if not strs:
              return ""
  
          length, count = len(strs[0]), len(strs)
          for i in range(length):
              c = strs[0][i]
              if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
                  return strs[0][:i]
  
          return strs[0]

  时间复杂度：O(mn)，空间复杂度：O(1)

  💡 二分查找

  首先，公共前缀长度不会长于最短子串。我们在 [0, minLength] 内进行二分查找。判断长度为 mid 的前缀相不相同。不相同的话则往前找，相同的话则往后找。判断前 mid 位是否相同的方式就可以用纵向扫描。此外，如果是往后找的话，前 mid 位就不用再判断了。

  class Solution:
      def longestCommonPrefix(self, strs: List[str]) -> str:
          def isCommonPrefix(length):
              str0, count = strs[0][:length], len(strs)
              return all(strs[i][:length] == str0 for i in range(1, count))
  
          if not strs:
              return ""
  
          minLength = min(len(s) for s in strs)
          low, high = 0, minLength
          while low < high:
              mid = (high - low + 1) // 2 + low
              if isCommonPrefix(mid):
                  low = mid
              else:
                  high = mid - 1
  
          return strs[0][:low]

  时间复杂度：O(mn * log(m))，其中 m 为最短字符串的长度，n 为字符串数量。空间复杂度：O(1)