dede网站模板下载,wordpress-seo,南江县规划和建设局网站,网站关键词和网站描述一、题目描述#xff1a;
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀#xff0c;返回空字符串 “”。 示例 1#xff1a; 输入#xff1a;strs [“flower”,“flow”,“flight”] 输出#xff1a;“fl” 示例 2#xff1a; 输入#xff1a;…一、题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 “”。 示例 1 输入strs [“flower”,“flow”,“flight”] 输出“fl” 示例 2 输入strs [“dog”,“racecar”,“car”] 输出“” 解释输入不存在公共前缀。
提示 1 strs.length 2000 strs[i].length 200strs[i] 仅由小写英文字母组成
二、解决思路和代码 解决思路 分析最长公共前缀的长度 小于等于 数组中最短字符串的长度 step1: 找到最短字符串的位置。step2: 将其余字符串中的字符与最短字符串中统一索引位置的字符进行匹配step3: 根据匹配信息返回最长匹配字符串 代码 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 idxminLengIdx: continuestrs_idx strs[idx]for i in range(len(strs_idx)):## 字符的索引值大于最短字符串的长度 或 同一索引下的字符不匹配当前字符串匹配结束if ilen(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]: breakresvalue[0] return res
