工信部网站备案规定,百度公司官网入口,自己做的网站涉黄,有那种做订单的网站吗题目#xff1a;
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀#xff0c;返回空字符串 。
思路A#xff1a;横向/纵向扫描
Python#xff1a;
class Solution:def longestCommonPrefix(self, strs: List[str]) - str:s …
题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串 。
思路A横向/纵向扫描
Python
class Solution:def longestCommonPrefix(self, strs: List[str]) - str:s if len(strs)2:return strs[0]for i in range(len(strs[0])):c strs[0][i]for j in range(1,len(strs)):if ilen(strs[j]) or c!strs[j][i]:return sscreturn s
思路B分治/二分
对于问题 可以分解成两个子问题 与 其中 。对两个子问题分别求解然后对两个子问题的解计算最长公共前缀即为原问题的解。
最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid判断每个字符串的长度为 mid 的前缀是否相同如果相同则最长公共前缀的长度一定大于或等于 mid如果不相同则最长公共前缀的长度一定小于 mid通过上述方式将查找范围缩小一半直到得到最长公共前缀的长度。
Python
class Solution:def longestCommonPrefix(self, strs: List[str]) - str:def lcp(start, end):if start end:return strs[start]mid (start end) // 2lcpLeft, lcpRight lcp(start, mid), lcp(mid 1, end)minLength min(len(lcpLeft), len(lcpRight))for i in range(minLength):if lcpLeft[i] ! lcpRight[i]:return lcpLeft[:i]return lcpLeft[:minLength]return if not strs else lcp(0, len(strs) - 1)class Solution:def longestCommonPrefix(self, strs: List[str]) - str:def isCommonPrefix(length):str0, count strs[0][:length], len(strs)return all(strs[i][:length] str0 for i in range(1, count))if not strs:return minLength min(len(s) for s in strs)low, high 0, minLengthwhile low high:mid (high - low 1) // 2 lowif isCommonPrefix(mid):low midelse:high mid - 1return strs[0][:low]
