Leetcode14. 最长公共前缀

一、题目描述：

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

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

1. 示例 1：

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

2. 示例 2：

   输入：strs = [“dog”,“racecar”,“car”]
   输出：“”
   解释：输入不存在公共前缀。

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

二、解决思路和代码

1. 解决思路

   • 分析：最长公共前缀的长度 小于等于 数组中最短字符串的长度
     • step1: 找到最短字符串的位置。
     • step2: 将其余字符串中的字符与最短字符串中统一索引位置的字符进行匹配
     • step3: 根据匹配信息，返回最长匹配字符串
       

2. 代码

   from typing import List
   class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:## 只有一个字符串，直接返回字符串if len(strs)==1: return strs[0]## step1: 找到最短字符串的位置。如果最短字符串的长度是0，直接返回""   minLengIdx = 0for idx in range(len(strs)):if len(strs[idx])<=len(strs[minLengIdx]):minLengIdx = idxif len(strs[minLengIdx])==0: return ""      ## step2: 以最短字符串为基准matchs = {}strsMinLengIdx = strs[minLengIdx]for idx in range(len(strsMinLengIdx)):matchs[idx] = [strsMinLengIdx[idx],True]## step3: 将其余字符串与最短字符串中的字符进行匹配     for idx in range(len(strs)):if idx==minLengIdx: continuestrs_idx = strs[idx]for i in range(len(strs_idx)):## 字符的索引值大于最短字符串的长度 或 同一索引下的字符不匹配，当前字符串匹配结束if i>=len(strsMinLengIdx) or not matchs[i][1]:breakif strs_idx[i]!=matchs[i][0]:matchs[i][1] = Falsebreak## step4: 返回最长匹配串res = "" for value in matchs.values():if not value[1]: breakres+=value[0]     return res