当前位置: 首页 > news >正文

Leetcode.1616 分割两个字符串得到回文串

题目链接

Leetcode.1616 分割两个字符串得到回文串 Rating : 1868

题目描述

给你两个字符串 ab,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由 a可以得到两个字符串: aprefixasuffix,满足 a = aprefix + asuffix,同理,由 b可以得到两个字符串 bprefixbsuffix ,满足 b = bprefix + bsuffix。请你判断 aprefix + bsuffix或者 bprefix + asuffix能否构成回文串。

当你将一个字符串 s分割成 sprefixssuffix时, ssuffix或者 sprefix可以为空。比方说, s = "abc"那么 "" + "abc""a" + "bc""ab"+ "c""abc"+ ""都是合法分割。

如果 能构成回文字符串 ,那么请返回 true,否则返回 false

注意, x + y表示连接字符串 xy

示例 1:

输入:a = “x”, b = “y”
输出:true
解释:如果 a 或者 b 是回文串,那么答案一定为 true ,因为你可以如下分割:
aprefix = “”, asuffix = “x”
bprefix = “”, bsuffix = “y”
那么 aprefix + bsuffix = “” + “y” = “y” 是回文串。

示例 2:

输入:a = “abdef”, b = “fecab”
输出:true

示例 3:

输入:a = “ulacfd”, b = “jizalu”
输出:true
解释:在下标为 3 处分割:
aprefix = “ula”, asuffix = “cfd”
bprefix = “jiz”, bsuffix = “alu”
那么 aprefix + bsuffix = “ula” + “alu” = “ulaalu” 是回文串。

提示:

  • 1<=a.length,b.length<=1051 <= a.length, b.length <= 10^51<=a.length,b.length<=105
  • a.length==b.lengtha.length == b.lengtha.length==b.length
  • ab都只包含小写英文字母

解法:双指针

我们考虑如何分割才能让 prefix + suffix组成一个回文串。

红色的部分就是已经匹配的了。
在这里插入图片描述

我们要讨论的就是 ab剩下的部分 sp

  • 如果 sp都为空,则 a_prefixb_suffix可以组成回文串。
  • 如果 sp不为空
    • 如果 sp是回文串,也可以成立
    • 如果 sp不回文串,那就不成立了

时间复杂度: O(n)O(n)O(n)

C++代码:

class Solution {
public:bool isValid(const string &s,int l,int r){for(int i = l,j = r;i < j;i++,j--){if(s[i] != s[j]) return false;}return true;}bool check(const string &a,const string &b){int n = a.size();int i = 0,j = n - 1;for(;i < j;){if(a[i] != b[j]) break;i++,j--;}return isValid(a,i,j) || isValid(b,i,j);}bool checkPalindromeFormation(string a, string b) {return check(a,b) || check(b,a);}
};

Python代码:

class Solution:def checkPalindromeFormation(self, a: str, b: str) -> bool:def isPalindrome(a:str,b:str) -> bool:i , j = 0 , len(a) - 1while i < j and a[i] == b[j]:i += 1j -= 1s = a[i:j+1]p = b[i:j+1]return s == s[::-1] or p == p[::-1]   return isPalindrome(a,b) or isPalindrome(b,a)

相关文章:

Leetcode.1616 分割两个字符串得到回文串

题目链接 Leetcode.1616 分割两个字符串得到回文串 Rating &#xff1a; 1868 题目描述 给你两个字符串 a和 b&#xff0c;它们长度相同。请你选择一个下标&#xff0c;将两个字符串都在 相同的下标 分割开。由 a可以得到两个字符串&#xff1a; aprefix和 asuffix&#xff0c…...

剑指 Offer II 033. 变位词组

题目链接 剑指 Offer II 033. 变位词组 mid 题目描述 给定一个字符串数组 strs&#xff0c;将 变位词 组合在一起。 可以按任意顺序返回结果列表。 注意&#xff1a;若两个字符串中每个字符出现的次数都相同&#xff0c;则称它们互为变位词。 示例 1: 输入: strs [“eat”,…...

spring-cloud-sentinel ---流控算法---review

计数器算法 计数器算法&#xff0c;限定每个固定时间能处理的请求总数&#xff0c;例如1分钟100&#xff0c;如果在第一个一分钟&#xff0c;总共请求60次&#xff0c;接着第二个一分钟&#xff0c;counter又会从0 开始技术&#xff0c;如果在1.5分钟的时候&#xff0c;达到了…...

1.浅析NIO 多路复用器selector

一&#xff1a;IO基本介绍 Java共支持3种网络编程IO模式&#xff1a;BIO&#xff0c;NIO&#xff0c;AIO 0.Java对BIO、NIO、AIO的支持&#xff1a; Java BIO &#xff1a; 同步并阻塞&#xff0c;服务器实现模式为一个连接一个线程&#xff0c;即客户端有连接请求时服务器端…...

Day920.结构化日志业务审计日志 -SpringBoot与K8s云原生微服务实践

结构化日志&业务审计日志 Hi&#xff0c;我是阿昌&#xff0c;今天学习记录的是关于结构化日志&业务审计日志的内容。 1、什么是结构化日志 结构化日志&#xff08;Structured Logging&#xff09;是一种将日志信息组织为结构化数据的技术。 传统的日志通常是一些文…...

前端代码复用学习笔记:整洁架构与清晰架构

基础代码的复用往往比较简单&#xff0c;但是业务代码的复用通常是困难的&#xff0c;如果没有特殊的手段去治理项目会逐渐发展为难以维护的巨石应用&#xff0c;按照维基百科记载&#xff0c;代码的复用形式主要有三种&#xff0c;程序库&#xff0c;应用框架&#xff0c;设计…...

【python刷题】leecode官方提示“->“,“:“这些符号是什么意思?什么是Type Hints?

作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&#xff0c;目前于海外某世界知名高校就读计算机相关专业。荣誉&#xff1a;阿里云博客专家认证、腾讯开发者社区优质创作者&#xff0c;在CTF省赛校赛多次取得好成绩。…...

【华为OD机试真题2023 JAVA】最佳对手

华为OD机试真题,2023年度机试题库全覆盖,刷题指南点这里 最佳对手 知识点排序DFS搜索回溯 时间限制:1s 空间限制:256MB 限定语言:不限 题目描述: 游戏里面,队伍通过匹配实力相近的对手进行对战。 但是如果匹配的队伍实例相差太大,对于双方游戏体验都不会太好。 给定n个…...

css实现文字大小自适应

在页面编写中经常会碰到页面自适应的问题&#xff0c;也就是页面内部的元素会随着窗口的放大缩小而放大缩小&#xff0c;box可以通过calc 百分比的形式做到页面自适应&#xff0c;但是box内的字体却无法做到这点&#xff0c;往往box自适应大小了&#xff0c;内部的字体还是原来…...

【Redis】搭建哨兵集群

目录 集群结构 准备实例和配置 启动 测试 集群结构 这里我们搭建一个三节点形成的Sentinel集群&#xff0c;来监管之前的Redis主从集群。如图&#xff1a; 三个sentinel实例信息如下&#xff1a; 节点IPPORTs1192.168.150.10127001s2192.168.150.10127002s3192.168.150.…...

CTFHub | .htaccess

0x00 前言 CTFHub 专注网络安全、信息安全、白帽子技术的在线学习&#xff0c;实训平台。提供优质的赛事及学习服务&#xff0c;拥有完善的题目环境及配套 writeup &#xff0c;降低 CTF 学习入门门槛&#xff0c;快速帮助选手成长&#xff0c;跟随主流比赛潮流。 0x01 题目描述…...

微机原理 || 8253 芯片 (详细讲解 + 经典例题)

一点点看&#xff01;一定可以看懂&#xff01;考试没有问题的&#xff01;加油&#x1f4aa; 前面知识写的详细&#xff0c;看不懂可以先看典例&#xff0c;回头来梳理就明白了【典例就是常考的题】 目录 Part 1: 芯片知识总结 &#xff08;一&#xff09;8253 芯片特点 …...

python Django高级操作-分页-定义CVS-发送邮件

分页 分页是指在web页面有大量数据需要显示&#xff0c;为了阅读方便在每个页页中只显示部分数据。优点: 1.方便阅读2.减少数据提取量&#xff0c;减轻服务器压力。Paginator对像 负责分页数据整体的管理对象的构造方法Paginator属性 Paginator方法 Paginator异常exception pag…...

React 用一个简单案例体验一遍 React-dom React-router React-redux 全家桶

一、准备工作 本文略长&#xff0c;建议耐心读完&#xff0c;每一节的内容与上一节的内容存在关联&#xff0c;最好跟着案例过一遍&#xff0c;加深记忆。 1.1 创建项目 第一步&#xff0c;执行下面的命令来创建一个 React 项目。 npx create-react-app react-example cd rea…...

9. C#面向对象基础

一、C# 类 在 C# 中&#xff0c;类是引用类型的。类由成员属性和成员方法构成。我们可以动态创建类的实例&#xff08;instance&#xff09;&#xff0c;这个实例也被称为对象&#xff08;object&#xff09;&#xff0c;我们可以通过类和对象来设计程序。 1、类的定义 类的定…...

【MIT 6.S081】Lab2: system calls

本Lab包括两个简单系统调用的实现&#xff0c;进一步熟悉系统调用接口。 笔者用时约1.5h 概述 根据文档说明&#xff0c;当我们添加一个系统调用时&#xff0c;比如第一个任务是添加一个trace&#xff0c;需要进行以下操作&#xff1a; 首先将系统调用的原型添加到user/user…...

设计模式之单例模式~

设计模式包含很多&#xff0c;但与面试相关的设计模式是单例模式&#xff0c;单例模式的写法有好几种&#xff0c;我们主要学习这三种—饿汉式单例&#xff0c;懒汉式单例、登记式单例,这篇文章我们主要学习饿汉式单例 单例模式&#xff1a; 满足要点&#xff1a; 私有构造 …...

top终端详解

1.top命令行使用 2.top每行意义 3.补充 1.top命令行使用 top命令是一个常用的Linux系统命令&#xff0c;用于实时查看系统的运行状态和进程信息。下面是top命令的几个常用参数的含义&#xff1a; -d seconds&#xff1a;设置top命令的更新间隔时间&#xff0c;单位是秒。默认是…...

解决一个偶现的503 bug,花了俺不少时间

概述 在3月2日晚上&#xff0c;大概8点左右&#xff0c;本想打道回府&#xff0c;回家休息&#xff0c;突然被人在bug群了一下&#xff0c;说是管理后台&#xff0c;访问不了&#xff0c;界面上出现了: 503 service temporarily unavailable我赶紧尝试访问了一下&#xff0c;确…...

什么是栈,如何实现?

欢迎来到 Claffic 的博客 &#x1f49e;&#x1f49e;&#x1f49e; “但有一枝堪比玉&#xff0c;何须九畹始征兰?” 前言&#xff1a; 栈是一种特殊的线性表&#xff0c;就像开盖的桶一样&#xff0c;从底部开始放数据&#xff0c;从顶部开始取数据&#xff0c;那么栈具体是…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...