image.png

算路：分治

  • 假如我只有两个字符串需要进行比较，那么算法是简单的，只要按部就班逐位比较即可
  • 如果不分治，那么也不困难，不断得到prefix和下一个进行比较就行
  • 分治的关键在于把大规模的问题缩减成小规模。
  • 可以把字符串数组分成两部分，左边的公共前缀left_prefix和右边的公共前缀right_prefix，那么只需要比较左右两边即可，利用递归可以实现。
  • 算法里用了嵌套函数，可以看看。

image.png

代码：

  1. class Solution:
  2.     # 分治算法实现
  3.     def longestCommonPrefix(self, strs: List[str]) -> str:
  4.         def lcp(begin_pos:int, end_pos:int)->str:
  5.             if end_pos == begin_pos:
  6.                 return strs[begin_pos]
  8.             mid = (begin_pos + end_pos) // 2
  9.             # 此时已经得到了左右两部分别的公共前缀
  10.             left_prefix, right_prefix = lcp(begin_pos, mid), lcp(mid + 1, end_pos)
  11.             # 希望得到当前的公共前缀
  12.             min_len = min(len(left_prefix), len(right_prefix))
  13.             prefix_index = 0
  14.             for i in range(min_len + 1):
  15.                 if i == min_len:
  16.                     prefix_index = min_len
  17.                 else:
  18.                     if left_prefix[i] != right_prefix[i]:
  19.                         prefix_index = i
  20.                         break
  21.             return left_prefix[:prefix_index]
  23.         return lcp(0, len(strs) - 1)