LeetCode 14. 最长公共前缀

写在前面

• 难度：简单

• 原文：https://leetcode-cn.com/problems/longest-common-prefix/

• 题目

   编写一个函数来查找字符串数组中的最长公共前缀。
   ​
   如果不存在公共前缀，返回空字符串 ""。
   ​
   示例 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

官方解释