Leetcode面试经典150_Q14最长公共前缀

题目:

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""


思路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 i>=len(strs[j]) or c!=strs[j][i]:
                    return s
            s+=c
        return s

思路B:分治/二分

对于问题 \textit{LCP}(S_i\cdots S_j),可以分解成两个子问题 \textit{LCP}(S_i \ldots S_{mid})\textit{LCP}(S_{mid+1} \ldots S_j),其中 mid=\frac{i+j}{2}。对两个子问题分别求解,然后对两个子问题的解计算最长公共前缀,即为原问题的解。

最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。可以在 [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) // 2
            lcpLeft, 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, minLength
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/527532.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Mac 每次重启终端都要重新配置mysql环境变量解决办法

1、问题 Mac 每次关闭终端后&#xff0c;mysql环境配置就失效了&#xff0c;需要重新配置mysql环境变量 2、解决方法 在 " ~/.zshrc "文件添加" source ~/.bash_profile "即可 vim ~/.zshrc source ~/.bash_profile 3、验证 退出终端后重新打开终端 mys…

PDF锐化

PDF Shaper Ultimate(pdf转图片) 编辑->添加文件->选中一个要处理的pdf 操作->转换->PDF转为图片 ComicEnhancerPro设置(把图片锐化) PDF Shaper Ultimate(图片转pdf) 编辑-添加图片->选中所有锐化处理后的图片 转换->图片转为pdf&#xff08;会把所有图…

3. Django 初探路由

3. 初探路由 一个完整的路由包含: 路由地址, 视图函数(或者视图类), 可选变量和路由命名. 本章讲述Django的路由编写规则与使用方法, 内容分为: 路由定义规则, 命名空间与路由命名, 路由的使用方式.3.1 路由定义规则 路由称为URL (Uniform Resource Locator, 统一资源定位符)…

Springboot使用教程

二、配置文件 SpringBoot使用一个全局的配置文件&#xff0c;配置文件名是固定的&#xff1b; •application.properties •application.yml 1.配置文件的作用&#xff1a; 修改SpringBoot自动配置的默认值&#xff1b;SpringBoot在底层都给我们自动配置好&#xff1b; Y…

HiveSQL之lateral view

lateral view是hiveQL中的一个高级功能&#xff0c;用于和表生成函数一起&#xff0c;来处理嵌套数组和结构的数据&#xff0c;特别是在处理复杂的数据结构如JSON或数组内嵌套数组时特别有用。它允许用户在每一行上应用TGF&#xff08;表生成函数&#xff09;&#xff0c;将生成…

再探Java为面试赋能(二)Java基础知识(二)反射机制、Lambda表达式、多态

文章目录 前言1.4 反射机制1.4.1 Class对象的获取1.4.2 Class类的方法1.4.3 通过反射机制修改只读类的属性 1.5 Lambda表达式1.5.1 函数式接口1.5.2 Lambda表达式的使用 1.6 多态1.6.1 多态的概念1.6.2 多态的实现条件1.6.3 重载&#xff08;Overload&#xff09;和重写&#x…

odoo16 安装

1、安装 /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" 2、安装git brew install git 3、安装python3 brew install python3 brew install python3.10 -- odoo16 如果用python3.12 - 会报错 brew unlink python3.1…

Python数学建模学习-莱斯利(Leslie)种群模型

Leslie模型是一种用于离散时间的生物种群增长模型&#xff0c;经常用于描述年龄结构对种群增长的影响。在1945年&#xff0c;人口生态学家Patrick H. Leslie&#xff08;莱斯利&#xff09;为了研究具有离散年龄结构的种群&#xff0c;特别是对于有不同年龄阶段的生物&#xff…

nginx This request has been blocked; the content must be served over HTTPS问题处理

This request has been blocked; the content must be served over HTTPS问题处理 1.问题现象2.解决问题3.解决后的现象4.proxy_set_header x-forwarded-proto 作用 1.问题现象 Mixed Content: The page at https://www.ssjxx.cn/ssjy/viy-edu/index.html?systemCodeTW0010#/…

电脑与多台罗克韦尔AB PLC无线通讯的搭建方法分为几步?

在实际系统中&#xff0c;同一个车间里分布多台PLC&#xff0c;通过上位机集中控制。通常所有设备距离在几十米到上百米不等。在有通讯需求的时候&#xff0c;如果布线的话&#xff0c;工程量较大耽误工期&#xff0c;这种情况下比较适合采用无线通信方式。本方案以组态王和2台…

OpenCV单通道图像按像素成倍比例放大(无高斯平滑处理)

OpenCV中的resize函数可以对图像做任意比例的放大(/缩小)处理&#xff0c;该处理过程会对图像做高斯模糊化以保证图像在进行放大&#xff08;/缩小&#xff09;后尽可能保留源图像所展现的具体内容&#xff08;消除固定频率插值/采样带来的香农采样信息损失&#xff09;&#x…

QML学习记录:并排页面切换效果的实现

定义一个ApplicationWindow窗口&#xff0c;通过添加SwipeView和PageIndicator来实现页面切换效果和显示当前页面位置的指示器。 ApplicationWindow {id:rootvisible: truewidth: 340height: 480title: qsTr("SwipeView") // 定义一个SwipeView用于页面切换效果 Swip…

支持向量机(SVM)白话之个人理解(学习记录)

本文仅有文字理解部分&#xff0c;没有相应的数学公式推导过程&#xff0c;便于新手理解。 一、什么是支持向量机 首先我们看下面这张图&#xff0c;在图中圆形和三角形分别代表不同的数据类型&#xff0c;如何画出一条直线使两者能够显著地区分开来呢&#xff1f; 答案可以多…

SSL数字证书基本概念

CA机构 CA机构&#xff0c;即证书授权中心&#xff08;Certificate Authority&#xff09;或称证书授权机构。CA认证中心作为电子商务交易中受信任的第三方&#xff0c;承担公钥体系中公钥合法性检验的责任。 SSL证书和SSL协议 安全套接层SSL&#xff08;Secure Sockets Lay…

基于GD32的简易数字示波器(3)- PCB设计

这期记录的是项目实战&#xff0c;做一个简易的数字示波器。 教程来源于嘉立创&#xff0c; 本期介绍PCB设计的大致流程。 下图为示波器的指标 具有选择交流耦合还是直流耦合功能、输入信号不衰减或衰减50倍 输入频率理论最大800KHz输入幅值&#xff08;不衰减&#xff09;…

03-JAVA设计模式-原型模式

原型模式 什么是原型模式 Java原型模式&#xff08;Prototype Pattern&#xff09;是一种创建型设计模式&#xff0c;其核心理念在于通过复制&#xff08;克隆&#xff09;已有的对象来创建新的对象&#xff0c;而不是通过构造函数来创建。 该模式可以显著提高对象创建的效率…

Web3的智能合约:未来合约的新范式

随着区块链技术的不断成熟和发展&#xff0c;智能合约作为其核心应用之一&#xff0c;正逐渐成为数字经济中的重要组成部分&#xff0c;引领着未来合约的新趋势。Web3的智能合约代表了一种全新的合约形式&#xff0c;其特点和应用将在未来产生深远影响。 智能合约的基本原理 智…

React - 你知道props和state之间深层次的区别吗

难度级别:初级及以上 提问概率:60% 如果把React组件看做一个函数的话,props更像是外部传入的参数,而state更像是函数内部定义的变量。那么他们还有哪些更深层次的区别呢,我们来看一下。 首先说props,他是组件外部传入的参数,我们知道…

皮具5G智能制造工厂数字孪生可视化平台,推进企业数字化转型

皮具5G智能制造工厂数字孪生可视化平台&#xff0c;推进企业数字化转型。随着信息技术的快速发展&#xff0c;数字化转型已成为企业提升竞争力、实现可持续发展的关键路径。皮具行业&#xff0c;作为一个传统的手工制造业&#xff0c;正面临着巨大的市场变革和技术挑战。如何在…

07 spring-cloud-gateway 的路由相关

前言 我们这里 大致梳理一下 spring-cloud-gateway 路由的相关处理 spring-cloud 微服务组件中的网关 这里主要分为几个 步骤 路由规则怎么获取如何路由网关过滤器的处理如何转发请求道下游微服务组件 路由规则怎么获取? GatewayAutoConfiguration 中包含了 spring-clou…