leetcode14.最长公共前缀

发布于 2021-04-17 05:40 ，所属分类：知识学习综合资讯

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串""。

示例

输入：strs = ["flower","flow","flight"]输出："fl"
输入：strs = ["dog","racecar","car"]输出：""解释：输入不存在公共前缀。

（左右滑动查看完整内容）

提示

0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]仅由小写英文字母组成

难度：简单
标签：字符串

分析和题解

方法一

1.最长公共前缀的特点：公共前缀必然存在于列表中的每一个字符串；

2.如果不存在公共前缀，返回空字符串""；

3.初始化公共前缀为列表的第一个元素，用公共前缀与列表第二个元素开始进行逐一对比每个字符，字符不一致时就取不一致之前的字符为公共前缀，不需要遍历剩余字符；

4.不用每次都比较整个字符串，只比较当前的公共前缀长度即可，因为公共前缀必然越来越小；如果公共前缀为空，就不需要遍历列表剩余的元素了。

class Solution:  def longestCommonPrefix(self, strs: List[str]) -> str:    if not strs: # 如果不存在公共前缀，返回空字符串 ""      return ""          public_res = strs[0] # 初始化公共前缀为列表的第一个元素    for ele in strs[1:]: # 从列表的第二个元素开始循环判断      len_res = len(public_res)      if len_res: # 如果公共前缀不为空，进行元素判断        for j in range(len(ele)):           # 循环遍历当前元素的每个字符，与公共前缀对应的字符进行判断          if j < len_res:            if ele[j] != public_res[j]:              public_res = public_res[:j] # 如果对应字符不一致，公共前缀就取对应字符之前的内容              break          else: break # 如果当前元素比公共前缀的长度长，超出的部分就不进行判断了        else:          public_res = ele      else: break # 如果公共前缀为空，就不用判断后面的字符串了    return public_res

（左右滑动查看完整代码）

方法二

1.找出列表中字典序最小和最大的字符串，因为这两个字符串的差别是最大的，最长公共前缀即为这两个字符串的公共前缀；

2.列表中的元素全部为字符串时，字符串比较采用的是 ”字典序“（通过 ASCII 对字符进行排序），即比较当前字符大小，若当前字符小则此字符串较小，若相等则继续往后比较，直到某一字符不相等或某一字符串比较结束，比较结束都相等，则长度小的字符串较小。

class Solution:  def longestCommonPrefix(self, strs: List[str]) -> str:    if not strs: # 如果不存在公共前缀，返回空字符串 ""      return ""
    strs.sort() # 列表从小到大排序    min_str = strs[0] # 列表中最小的字符串    max_str = strs[-1] # 列表中最大的字符串    '''    这两行相当于上面三行代码    min_str = min(strs) # 列表中最小的字符串    max_str = max(strs) # 列表中最大的字符串    '''
    for i in range(len(min_str)):      if min_str[i] != max_str[i]:        return min_str[:i] # 如果对应字符不一致，公共前缀就取对应字符之前的内容    return min_str

（左右滑动查看完整代码）

方法三

1.取列表中每个字符串相同下标的字符, 看是否相同；

2.zip(*str) 将 str 中所有字符串并列到迭代器中，逐次并列返回 str 中所有字符串相同下标的字符合并成的元组（元组个数与最短的字符串长度一致）；

3.通过set()去重，判断每个字符串相同下标的字符是否相同，如果相同就把这个字符放在公共前缀中。

class Solution:    def longestCommonPrefix(self, strs: List[str]) -> str:        public_res = ''        for i in zip(*strs):  # 使用 zip 根据字符串下标合并成元组            if len(set(i)) == 1:  # 把元组通过 set 去重，判断元组中元素是否都相同                public_res += i[0]  # 如果相同就把这个元素放在公共前缀中            else:                break        return public_res