(回溯) 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)

喜欢的话给个关注吧!!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

后端Web开发之Maven

1.java项目构建工具maven介绍 Maven是apache旗下的一个开源项目。Apache软件基金会&#xff0c;成立于1999年7月&#xff0c;是目前世界上最大的最受欢迎的开源&#xff08;源代码开放&#xff09;软件基金会也是一一个专门为支持开源项目而生的非盈利性组织。 apache开源项目…

PDO在CANopen协议同步传输和异步传输

PDO&#xff08;过程数据对象&#xff09;在CANopen协议中有两种主要的传输方式&#xff1a;同步传输和异步传输。这两种方式决定了PDO数据的传输时机和条件。下面分别举例说明这两种传输方式&#xff1a; 1. 同步传输 (Synchronous Transmission) 概念&#xff1a; 在同步传输…

3GPP 4G 5G 主要协议

4G LTE的协议主要是36 series 5G NR的协议主要是38 series

RustScan:开源端口扫描器

RustScan 是一款开源端口扫描器&#xff0c;专为速度和多功能性而设计。 它结合了时尚的界面和随时间推移而适应和改进的能力。 借助 RustScan 的自适应学习功能&#xff0c;该工具不断优化其性能&#xff0c;使其成为最高效的端口扫描器。 在几秒钟内发现开放端口&#xff…

解决端口号被占用问题

第一种&#xff1a; 最简单有效的方法&#xff0c;重启一下电脑&#xff0c;占用此端口的程序就会释放端口。 第二种&#xff1a; 使用命令找到占用端口的程序&#xff0c;把它关闭。 1、打开运行窗口输入&#xff1a;CMD &#xff0c;进入命令窗口。 2、输入&#xff1a;n…

Candance Allegro 入门教程笔记:如何绘制原理图和原理图库?

文章目录 一、用 Capture CIS 17.4 绘制原理图库 Cadence Allegro QQ交流学习裙&#xff1a;173416628 1、凡亿教育的Candance Allegro 17.4基础教程 2、小哥Cadence Allegro 132讲 技巧视频 3、小哥Cadence Allegro 两层板 基础视频 4、小哥Cadence Allegro 四层板 提高视频…

23.10 Django 事务的使用

1. 事务 事务(Transaction): 是一种将多个数据库操作组合成一个单一工作单元的机制. 如果事务中的所有操作都成功完成, 则这些更改将永久保存到数据库中. 如果事务中的某个操作失败, 则整个事务将回滚到事务开始前的状态, 所有的更改都不会被保存到数据库中. 这对于保持数据的…

3.串口(UART)

串口理论部分可看51部分&#xff1a;链接 数据帧 帧头(2字节&#xff0c;例如AA、BB) 数据长度&#xff08;2字节&#xff09; 数据 CRC16校验&#xff08;2字节&#xff09; 帧尾&#xff08;2字节&#xff09; 代码编写 串口一发送命令控制LED灯(PB5、PE5) LED灯、串口、…

【书生·浦语大模型实战营】第三期 入门岛作业

入门岛作业 Linux闯关任务&#xff1a;完成 SSH 连接与端口映射并运行 hello_world.py。配置vscode作业内容 可选任务1&#xff1a;将Linux基础命令在开发机上完成一遍作业内容 可选任务 2&#xff1a;使用 VSCODE 远程连接开发机并创建一个conda环境作业内容 可选任务 3&#…

Selenium + Python 自动化测试10(unittest概念)

我们的目标是&#xff1a;按照这一套资料学习下来&#xff0c;大家可以独立完成自动化测试的任务。 上几篇我们讨论了元素的定位方法、操作方法以及一些特殊元素的操作。 在实际的测试项目组中每个模块会写多条案例&#xff0c;如第一条用例那里我们的登录。登录的话就可以有多…

面试经典算法150题系列-接雨水

接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,…

doxygen制作接口文档

系列文章目录 文章目录 系列文章目录前言一、下载二、安装三、代码注释四、使用doxygen生成文档 前言 每次手动写接口文档太痛苦了&#xff0c;现在福利来了–doxygen Doxygen是软件开发中广泛使用的文档生成器工具。它自动从源代码注释生成文档&#xff0c;解析有关类、函数和…

LVS原理详解及部署

目录 一、LVS原理 1.LVS简介 2.LVS结构 3.IP负载均衡技术 4.LVS相关术语 二、LVS负载均衡四种工作模式 1.LVS-DR模式 2.LVS-NAT模式 3.LVS-TUN模式&#xff08;了解&#xff09; 4.FULL-NAT模式&#xff08;了解&#xff09; 三、LVS负载均衡十种调度算法 四、LVS部…

学习大数据DAY35 利用 echarts 的开源图表和 python 异常处理优化网站

目录 根据分数统计电影数量来生成图表 上机练习 14 添加异常 添加电影类型判断是整数及正整数异常 部署项目到 Nginx 上机练习 15 根据分数统计电影数量来生成图表 Echarts 官网&#xff1a; https://echarts.apache.org/examples/zh/index.html 下载柱状图和饼图 可以…

Java Enum类笔记

Java系列文章目录 文章目录 Java系列文章目录一、前言二、学习内容&#xff1a;三、问题描述四、解决方案&#xff1a;五、总结&#xff1a;5.1 学习总结&#xff1a; 一、前言 学习Enum类的笔记 二、学习内容&#xff1a; Eunm类的实操 三、问题描述 Eunm枚举的使用 四、解…

Datawhale X 魔搭 AI夏令营第四期-魔搭生图task1学习笔记

根据教程提供的链接&#xff0c;进入相应文章了解魔搭生图的主要工作是通过对大量图片的训练&#xff0c;生成自己的模型&#xff0c;然后使用不同的正向、反向提示词使模型输出对应的图片 1.官方跑baseline教程链接:Task 1 从零入门AI生图原理&实践 2.简单列举一下赛事的…

MongoDB教程

目录 介绍启动命令命令行操作常用命令总结MongoDB Compass 介绍 MongoDB是一个基于分布式文件存储的开源数据库系统&#xff0c;由C语言编写&#xff0c;旨在为WEB应用提供可扩展的高性能数据存储解决方案。MongoDB将数据存储为一个文档&#xff0c;数据结构由键值对组成&…

ibis:极具潜力的Python数据分析新框架

今天要给大家介绍的Python框架叫做ibis&#xff0c;没错&#xff0c;跟著名连锁酒店宜必思同名&#xff0c;其作者是创造了pandas、Arrow等著名框架的Wes McKinney。 ibis的核心理念是用同一套数据框操作API&#xff0c;统一操纵各种主流的数据运算框架&#xff0c;使得用户可以…

Ubuntu安装 IDEA

一、在官网下载 IDEA 下载IDEA For LinuxDownload the latest version of IntelliJ IDEA for Windows, macOS or Linux.https://www.jetbrains.com/idea/download/?sectionlinux下载好的安装包解压到/opt/中&#xff0c;目录名更改为 idea 二、对/opt/idea 目录下所有文件授予…

canal监听mysql增量数据发布到rabbitmq

canal工作原理 canal 依靠mysql主从备份的原理&#xff0c;模拟 MySQL slave 的交互协议&#xff0c;伪装自己为 MySQL slave &#xff0c;向 MySQL master 发送dump 协议MySQL master 收到 dump 请求&#xff0c;开始推送 binary log 给 slave (即 canal )canal 解析 binary …