本文共 1977 字,大约阅读时间需要 6 分钟。
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"] 输出: "fl"示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z
方解题分析:
最长公共前缀指的是字符串数组中所有公共最长的前缀。
如果是空串的话,那么说明前缀就是“” 如果都是以“ ”开头的,那么就是“ ”因为最长的前缀不会超过最短的字符串,那么可以遍历最短的字符串的长度,依次比较。
第一步:找出长度最短的字符串;第二步:依次与长度最短的字符串比较法分析:
方法一:
if not strs: return ""if len(strs) == 1: return strs[0]minl = min([len(x) for x in strs])end = 0 while end < minl:for i in range(1,len(strs)): if strs[i][end]!= strs[i-1][end]: return strs[0][:end]end += 1return strs[0][:end]
方法二:
res = ""if len(strs) == 0: return ""for each in zip(*strs): #zip()函数用于将可迭代对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表 if len(set(each)) == 1: #利用集合创建一个无序不重复元素集 res += each[0] else: return resreturn res
方法三:
class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ rstr = '' if strs == []: return rstr old = strs[0] for i in range(len(old)): #i为第一个元素的遍历单个字符 for j in range(len(strs)): try: if old[i] == strs[j][i]: pass else: return rstr except: return rstr else: rstr += old[i] return rstr
思路二:
这个思路比较简单了,直接抽出一个单词来,取其不同长度的从头开始的子串然后看看其他字符串是不是以这个字符串开头的,如果是就继续取更长的子串,如果不是就直接返回上一次子串的长度就OK了
class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0) return ""; for(int i=1;i<=strs[0].length();i++){ String head = strs[0].substring(0,i); for(String str:strs){ if(!str.startsWith(head)) return head.substring(0,i-1); } } return strs[0]; }}
总结:
1. 不需要求出最短字符串是哪个,只需要求出最短字符串的长度即可。
2. 字符串组的几种情况的判断应更清晰明了。 1)字符串组为空 [] 2)公共字符串为空[ ”,”] 3) 按正常情况来做转载地址:http://bjfgi.baihongyu.com/