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

(回溯) LeetCode 131. 分割回文串

原题链接

一. 题目描述

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

二. 解题思路

首先得明确什么是回文串,回文串就是能够对称的字符串,还是老样子。

1. 明确递归参数:字符串s 和当前路径的起点 startindex 。

2. 确定递归的终止条件:当startindex 的大小超过字符串的长度的时候终止,证明已经切割到了字符串的最后,直接将path 路径添加到结果数组res 中即可,这里小伙伴可能要问了,你这还没有判断是不是回文串,对,因为我在后面的单层递归中做了限制,只有回文子串才能进path 数组。所以这里的path 数组中一定是回文子串。

3. 单层递归逻辑:相信做了这么多的题目了,一定知道怎么写吧,只需要加一条判断是不是回文子串的限制条件即可,如果是将其加入到path 数组中进行递归即可,如果不是直接continue;最后做好回溯即可。

话不多说!!!上代码!!

三. 代码

class Solution {
public:vector<vector<string>> res;vector<string> path;bool isPalindrome(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;}void back(string s, int startindex){if(startindex >= s.size()){res.push_back(path);return;}for(int i = startindex; i < s.size(); i++){if(isPalindrome(s, startindex, i)){string str = s.substr(startindex, i - startindex + 1);path.push_back(str);back(s, i + 1);path.pop_back();    // 回溯}}}vector<vector<string>> partition(string s) {back(s, 0);return res;}
};

四. 总结

如果你将前面的题目做了练习的话相信这类题目已经非常简单了吧!!!继续加油!!!

时间复杂度:O(n * 2^n)

空间复杂度:O(n^2)

喜欢的话给个关注吧!!

相关文章:

(回溯) LeetCode 131. 分割回文串

原题链接 一. 题目描述 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串。返回 s 所有可能的分割方案。 示例 1&#xff1a; 输入&#xff1a;s "aab" 输出&#xff1a;[["a","a","b"],[…...

【Linux】阻塞信号|信号原理|深入理解捕获信号|内核态|用户态|sigaction|可重入函数|volatile|SIGCHILD|万字详解

目录 ​编辑 一&#xff0c;常见的信号术语 二&#xff0c;信号在内核中的表示 信号标志位 Pending表 Block表 handler表 POSIX.1标准 三&#xff0c;sigset_t 信号集操作函数 sigemptyset sigfillset sigaddset sigdelset sigismember sigprocmask sig…...

基于Linux对 【进程地址空间】的详细讲解

研究背景&#xff1a; ● kernel 2.6.32 ● 32位平台 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 在学习操作系统中想必大家肯定都见过下面这…...

[python]使用Pandas处理多个Excel文件并汇总数据

在数据分析和处理过程中&#xff0c;经常需要处理多个Excel文件&#xff0c;并将其中的数据进行汇总和分析。本文介绍使用Python的Pandas库来读取多个Excel文件&#xff0c;并汇总不同类型的数据&#xff0c;例如员工工资、工件数量等。 代码示例 以下是一个完整的代码示例&a…...

提升体验:UI设计的可用性原则

在中国&#xff0c;每年都有数十万设计专业毕业生涌入市场&#xff0c;但只有少数能够进入顶尖企业。尽管如此&#xff0c;所有设计师都怀揣着成长和提升的愿望。在评价产品的用户体验时&#xff0c;我们可能会依赖直觉来决定设计方案&#xff0c;或者在寻找改善产品体验的切入…...

x264 编码器 SSIM 算法源码分析

SSIM SSIM(Structural Similarity Index)是一种用于衡量两幅图像之间视觉相似度的指标。它不仅考虑了图像的亮度、对比度和饱和度,还考虑了图像的结构信息。SSIM的值介于-1到1之间,值越接近1表示两幅图像越相似。 SSIM是基于以下三个方面来计算的: 亮度(Luminance):比…...

echarts使图表组件根据屏幕尺寸变更而重新渲染大小

效果图&#xff1a; 通过 window.addEventListener(resize, this.resizeChart); 实现 完整代码&#xff1a; <template><div class"dunBlock"><div class"char2" id"char2" ref"chart"></div></div…...

电脑图片损坏打不开怎么办?能修复吗?

照片和视频是记录和保存现实生活中的事件的最好方式。由于手机储存空间有限&#xff0c;一般我们会把有纪念意义的照片放到电脑上进行保存&#xff0c;但有时难免会遇到照片被损坏打不开的情况&#xff0c;一旦遇到这种情况&#xff0c;先不要急&#xff0c;也不要因为照片打不…...

vue-cli(二)

箭头函数 一般的函数&#xff1a; 这里window是用来调用函数的 function fun(){console.log(this) } window.fun(); 箭头函数&#xff1a; 1、如果只有一个参数&#xff0c;形参的小括号可以省略 2、如果只有一条语句&#xff0c;{}可以省略 完整的写法 let fun2 a>…...

今日头条的账号id在哪里看(网页版)

今日头条的账号id在哪里看&#xff08;网页版&#xff09; 1.https://mp.toutiao.com/profile_v4/index2.登录今日头条账号3.设置->头条号ID 1.https://mp.toutiao.com/profile_v4/index 2.登录今日头条账号 3.设置->头条号ID 打开下方链接&#xff1a; https://mp.to…...

单体应用提高性能和高并发处理-合理使用多核处理

合理使用多核处理能力是提升单体应用性能和处理高并发能力的重要手段。以下是关于如何合理利用多核处理器的详细讲解&#xff0c;包括多线程编程、线程池的使用、并行计算、以及如何避免常见的性能陷阱。 1. 多线程编程 多线程编程是利用多核处理器的直接方式。每个线程可以在…...

基于STM32/GD32的双CAN、一路485开发板

双CAN开发板 双CAN、一路485开发板的设计开发板配置器件选型CAN设计硬件设计软件设计 485设计硬件设计软件设计 其他设计LED硬件按键硬件 PCB板子和实物图开发板测试视频其他资料 双CAN、一路485开发板的设计 最近工作经常会出现一些小问题。就想设计一款带CAN的开发板用来测试…...

快排/堆排/归并/冒泡/

常见的内排序算法 插入排序 直接插入排序 原理&#xff1a;相当于扑克牌变成有序&#xff0c;先拿第一张&#xff0c;把他调节成有序&#xff0c;再拿第二张&#xff0c;与第一张相比找到第二张的位置&#xff0c;再继续拿第三张&#xff0c;以此类推。 void InsertSort(in…...

React基础教程(08):state体验

文章目录 7、state再体验7.1 异步更新状态7.2 同步更新状态方式17.3 同步更新状态方式27.4 betterScroll7.5 列表案例7、state再体验 7.1 异步更新状态 完整代码 import React from "react";export default class App extends React.Component{state = {count:1,}…...

Win10 创建新的桌面2,并实现桌面切换

1. Win10 创建新的桌面2 Win - Tab 2. Win10 桌面切换 Ctrl - Win - ←/→ 我们下期见&#xff0c;拜拜&#xff01;...

MySQL数据库介绍及基础操作

目录&#xff1a; 一.数据库介绍 二.数据库分类 三. 数据库的操作 四. 常用数据类型 五. 表的操作 一.数据库介绍 1.文件保存数据有以下几个缺点: 1.1文件的安全性问题 1.2文件不利于数据查询和管理 1.3文件不利于存储海量数据 1.4文件在程序中控制不方便 为了解决上述问题&…...

【C语言篇】C语言常考及易错题整理DAY2

文章目录 C语言常考及易错题整理选择题编程题至少是其他数字两倍的最大数两个数组的交集图片整理寻找数组的中心下标多数元素除自身以外数组的乘积不使用加减乘除求两个数的加法 C语言常考及易错题整理 选择题 下列 for 循环的次数为&#xff08; &#xff09; for(int i 0…...

javase入门

最近在学习大数据,学到flume拦截器的时候发现自定义拦截器需要使用java编写,现在开始学一些java入门的东西. 一. java相关组成 path环境变量: 环境变量用于记住程序路径,方便在命令行窗口任意目录启动程序. 二 java中的变量 变量要先定义在使用. int age 15 定义变量要定义其…...

Wireshark显示过滤器大全:快速定位网络流量中的关键数据包

文章目录 一、简介二、wireshark中的逻辑运算符三、过滤示例集合3.1 过滤指定日期和时间3.2 过滤指定协议3.2.1 例&#xff1a;仅显示SMTP&#xff08;端口 25&#xff09;和ICMP流量&#xff1a;3.2.2 例如&#xff1a;Windows 客户端 - DC 交换 3.3 过滤指定网段&#xff08;…...

OOP笔记4----抽象类、接口、枚举

抽象类 简介 父类可以封装不同子类的共同特征或者共同行为.而有的时候&#xff0c;父类中封装的方法无法具体完成子类中需要的逻辑&#xff0c;因此我们可以将此方法设计成抽象方法&#xff0c;即使用关键字abstract进行修饰。而有抽象方法的类&#xff0c;也必须使用abstract…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...