写在前面
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"] 输出: "fl" 示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明: 所有输入只包含小写字母 a-z 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1
可以简化为2个字符串求交集，然后用结果去对余下的所有的字符串依次求解，有个递归的过程。 对2个字符串求交集，先算出来长度小的那个字符串，对其遍历，返回公共部分，没有就返回空串。 注意点 1. 如果长度为0就返回空 2. 如果长度为1，就返回唯一的字符串 3. 如果长度超过2，那么就比较，用reduce反复求
参考代码1
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if len(strs)==0:return "" if len(strs)==1:return strs[0] else: def shortString(s1,s2): """这个函数的目的就是返回2个字符串的公共部分""" result = "" for i in range(len(s1)): if not s2.startswith(s1[:i+1]): break else: result = s1[:i+1] return result from functools import reduce return reduce(shortString,strs)
- 分析
效率肯定是比较差的，明显多做了很多事情，比如比较到第一个第二个的时候如果就错了，那根本无需做下去。
垂直扫描法
可以把列表中的字符串纵向对比，依次比较每个字符串的第一位，如果都一样就做下一个，否则就退出。 ["flower","flow","flight"] 竖着排 flower flow flight 怎么比较是否一样呢，利用zip函数竖排得到tuple，再转换set如果长度为1就是一样。
参考代码2
class Solution: def longestCommonPrefix(self, strs: list) -> str: if len(strs)==0:return "" if len(strs)==1:return strs[0] zip_strs = zip(*strs) result = "" for i in zip_strs: if len(set(i))==1: result = result + i[0] else: break return result
官方解释
Original: https://www.cnblogs.com/wuxianfeng023/p/16598466.html
Author: 松勤吴老师
Title: LeetCode 14. 最长公共前缀
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/602607/
转载文章受原作者版权保护。转载请注明原作者出处！