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

leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记

131. 分割回文串 - 力扣(LeetCode)

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

示例 1:

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

示例 2:

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

>>思路和分析:

  1. 切割问题,有不同的切割方式
  2. 判断回文

代码随想录的Carl老师说:“切割问题类似组合问题”!(这段文字来自代码随想录--分割回文串)

对于字符串abcdef

  • 组合问题选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....
  • 切割问题切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....

>>回溯三部曲:

1).确定回溯函数参数

  • path 存放切割后回文的子串
  • result 保存 path,作为结果集
  • startIndex 来控制for循环的起始位置(表示下一轮递归遍历的起始位置),还用来表示这条切割线.(切割过的地方,不能重复切割,和组合问题也是保持一致的【这句话来自代码随想录】)
vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
void backtracking (const string& s, int startIndex) // startIndex 就用来表示这条切割线

2).递归的终止条件

如果切割线切到了字符串最后面,表示找了一种切割方法,此时终止本层递归!也就是出现这种情况: startIndex >= s.size(),收集结果后直接return;

void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}
}

3).单层搜索的逻辑

>>问题(O_O)?思考:在递归循环中如何截取子串呢?

  • [startIndex,i]:左闭右闭,表示子串的起始位置和终止位置,有截取区间就可以截取子串。substr(startIndex, i - startIndex + 1);

>>问题(O_O)?思考:如何判断所截取子串是否为回文子串呢?

  1. 判断是否为回文子串:isPalindrome(s, startIndex, i),用双指针法
  2. 如果是回文,就加入在vector<string> path中,path 用来记录切割过的回文子串
for (int i = startIndex; i < s.size(); i++) {if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);} else {                // 如果不是则直接跳过continue;}backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back();        // 回溯过程,弹出本次已经添加的子串
}

注意:切割过的位置,不能重复切割,应传入下一层的起始位置为 i + 1,即

  • backtracking(s, i + 1);

 (1)判断是否为回文子串

bool isPalindrome(const string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}
bool isPalindrome(string s) {int left = 0,right = s.size()-1;while(left<=right) {if (s[left] != s[right]) return false;left++;right--;}return true;
}

 (2)C++代码

class Solution {
private:vector<vector<string>> result;vector<string> path; // 放已经回文的子串void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}for (int i = startIndex; i < s.size(); i++) {if (isPalindrome(s, startIndex, i)) {   // 是回文子串// 获取[startIndex,i]在s中的子串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);} else {                                // 不是回文,跳过continue;}backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back(); // 回溯过程,弹出本次已经添加的子串}}bool isPalindrome(const string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}
public:vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n^2)
class Solution {
public:vector<vector<string>> result;vector<string> path; // 放已经回文的子串bool isPalindrome(string s) {int left = 0,right = s.size()-1;while(left<=right) {if (s[left] != s[right]) return false;left++;right--;}return true;}void backtracking(string s,int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if(startIndex >= s.size()) {result.push_back(path);return;}for(int i=startIndex;i<s.size();i++) {// 获取[startIndex,i]在s中的子串string subStr = s.substr(startIndex,i-startIndex+1);if(isPalindrome(subStr)) path.push_back(subStr);// 是回文子串else continue;// 不是回文,跳过backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back(); // 回溯过程,弹出本次已经添加的子串}}vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};

 参考和推荐文章、视频:
带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1c54y1e7k6/?p=67&spm_id_from=pageDriver代码随想录 (programmercarl.com)icon-default.png?t=N7T8https://www.programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E4%BC%98%E5%8C%96

相关文章:

leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记

131. 分割回文串 - 力扣&#xff08;LeetCode&#xff09; 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串 示例 1&#xff1a; 输入&#xff1a;s "aa…...

浅谈对于Android CMakeLists文件的理解

文章目录 文件结构 文件结构 cmake_minimum_required(VERSION 3.10.2) //设置cmake版本set(CMAKE_LIBRARY_OUTPUT_DIRECTORY${CMAKE_CURRENT_LIST_DIR}/../jniLibs/${ANDROID_ABI}) //设置.so文件输出路径 project("add") //编译目录add_library( common //生成.so文…...

虚函数可不可以重载为内联 —— 在开启最大优化时gcc、clang和msvc的表现

下面是对该问题的一种常见回答&#xff1a; 首先&#xff0c;内联是程序员对编译器的一种建议&#xff0c;因此可以在在重载虚函数时在声明处加上inline关键字来修饰&#xff0c; 但是因为虚函数在运行时通过查找虚函数表调用的&#xff0c;而内联函数在编译时进行代码嵌入&…...

【开源】基于Vue+SpringBoot的智能教学资源库系统

项目编号&#xff1a; S 050 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S050&#xff0c;文末获取源码。} 项目编号&#xff1a;S050&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课…...

Sass基础知识之【变量】

文章目录 前言变量声明变量引用变量名用中划线还是下划线分隔后言 前言 hello world欢迎来到前端的新世界 &#x1f61c;当前文章系列专栏&#xff1a;Sass和Less &#x1f431;‍&#x1f453;博主在前端领域还有很多知识和技术需要掌握&#xff0c;正在不断努力填补技术短板。…...

云原生系列Go语言篇-泛型Part 1

“Don’t Repeat Yourself”是常见的软件工程建议。与其重新创建一个数据结构或函数&#xff0c;不如重用它&#xff0c;因为对重复的代码保持更改同步非常困难。在像 Go 这样的强类型语言中&#xff0c;每个函数参数及每个结构体字段的类型必须在编译时确定。这种严格性使编译…...

力扣1089题 复写零 双指针解法

2. 复写零 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改&#xff0c;不要从函数返回任何东西。 示例 1&…...

Redis基础与运用

一、redis介绍 简介 Redis 是完全开源的&#xff0c;遵守 BSD 协议&#xff0c;是一个高性能的 key-value 数据库。 Redis 与其他 key - value 缓存产品有以下三个特点&#xff1a; Redis支持数据的持久化&#xff0c;可以将内存中的数据保存在磁盘中&#xff0c;重启的时候可…...

PTA:猜帽子游戏 ,C语言

题目 宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子&#xff0c;有的是黑色的&#xff0c;有的是黄色的。每个人可以看到别人头上的帽子&#xff0c;但是看不到自己的。游戏开始后&#xff0c;每个人可以猜自己头上的帽子是什么颜色&#xff0c;或者可以弃权不猜。如…...

ESP32基于IDF框架OTA学习记录

ESP32基于IDF框架OTA学习记录 参考&#xff1a; 空中升级 (OTA) - ESP32 - — ESP-IDF 编程指南 v5.1.1 文档 (espressif.com) 目录 ESP32基于IDF框架OTA学习记录1.分区表2.native_ota_example上手2.1配置分区表2.2配置OTA的bin文件2.3修改esp32的https证书验证方法2.4修改当…...

分布式技术(一)分布式的架构的演进

&#x1f48c; 所属专栏&#xff1a;【微服务】&#x1f600; 作 者&#xff1a;长安不及十里&#x1f4bb; 工作&#xff1a;目前从事电力行业开发&#x1f308; 目标&#xff1a;全栈开发&#x1f680; 个人简介&#xff1a;一个正在努力学技术的Java工程师&#xff0c;专注基…...

webpack 打包优化

在vue.config.js中配置 下载 uglifyjs-webpack-plugin 包 const { defineConfig } require("vue/cli-service"); var path require("path");module.exports defineConfig({transpileDependencies: true,filenameHashing: false, // 去除Vue打包后.cs…...

electron windows robotjs 安装教程

Robotjs 安装 前言第一步 : 安装python第二步 : 安装Visual Studio 2022第三步 : 安装robotjs 前言 robotjs可以控制鼠标键盘&#xff0c;获取屏幕内容&#xff0c;配合electron可做很多自动化操作。windows下配置环境有很多坑&#xff0c;很多文章都太旧了。试了很多次发现了…...

IDEA解决Git冲突详解

目录 前言&#xff1a; 何为冲突 冲突演示 IDEA冲突解决 小结&#xff1a; 前言&#xff1a; 相信大家多多少少都有了解和使用过Git&#xff0c;作为Java程序员idea可谓是无敌的存在了&#xff0c;那么如何使用idea解决Git冲突呢&#xff1f;不瞒大家前段时间在公司把同事…...

Vue3使用kkFileView预览文件pdf

kkFileView - 在线文件预览kkFileView官网 - kkFileView使用Spring Boot搭建&#xff0c;易上手和部署&#xff0c;基本支持主流办公文档的在线预览&#xff0c;如doc,docx,Excel,pdf,txt,zip,rar,图片等等https://kkfileview.keking.cn/zh-cn/docs/usage.html业务场景&#xf…...

建造者模式-C语言实现

UML类图&#xff1a; 代码实现&#xff1a; #include <stdio.h> #include <stdlib.h>// 产品类 typedef struct {char* part1;char* part2;char* part3; } Product;// 抽象建造者类 typedef struct {void (*buildPart1)(void*, const char*);void (*buildPart2)(v…...

Jmeter+influxdb+grafana监控平台在windows环境的搭建

原理&#xff1a;Jmeter采集的数据存储在infuxdb数据库中&#xff0c;grafana将数据库中的数据在界面上进行展示 一、grafana下载安装 Download Grafana | Grafana Labs 直接选择zip包下载&#xff0c;下载后解压即可&#xff0c;我之前下载过比较老的版本&#xff0c;这里就…...

关注这两点 或能避开一些现货黄金交易的陷阱

在现货黄金投资中&#xff0c;交易机会是处处都有&#xff0c;但是亏损的情况也可能出现。投资者要在陷阱处处的市场中获得稳定盈利&#xff0c;就需要懂得如何规避现货黄金投资的陷阱。下面我们就来介绍两个很常用的避开陷阱的方法。 看交易的活跃度。交易越活跃&#xff0c;市…...

Python 文件读写

Python 文件读写笔记整理 参数说明 open(path, flag[, encoding][,errors]) path:要打开文件的路径 flag:打开方式 encoding:编码方式 errors:错误处理 Flag打开方式表 模式 描述 r 以只读方式打开文件。文件的指针将会放在文件的开头。这是默认模式。 rb 以二进制格…...

线性分组码的奇偶校验矩阵均匀性分析

回顾信道编解码知识&#xff0c;我们知道信道编码要求编码具有检纠错能力&#xff0c;作为FEC&#xff08;forward error correction&#xff09;前向纠错编码的一类&#xff0c;线性分组码表示校验位与信息位的关系能够线性表示。 在这篇文章中&#xff0c;并不是要讨论信道编…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...