力扣日记1.27-【回溯算法篇】131. 分割回文串

力扣日记:【回溯算法篇】131. 分割回文串

日期:2023.1.27
参考:代码随想录、力扣

131. 分割回文串

题目描述

难度:中等

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

回文串 是正着读和反着读都一样的字符串。

示例 1:

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

示例 2:

输入:s = “a”
输出:[[“a”]]

提示:

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

题解

class Solution {
public:// 关键:将切割问题类比转换为组合问题(树状图)// 但切割与组合最大的不同在于横向遍历时,组合是从集合中取单个值,但切割是截取一个子串 -> for循环时,[startindex, i]表示当前截取的子串(左闭右闭)vector<vector<string>> results; // 组合的集合vector<string> path;    // 存储回文子串的组合vector<vector<string>> partition(string s) {backtracking(s, 0);return results;}// 如何判断回文串(双指针,一个从头往后,一个从尾往前,对应相等则为回文串)bool isPalindrome(string s, int startindex, int endindex) {// 左闭右闭while (startindex < endindex) {if (s[startindex] != s[endindex]) {return false;}startindex++;endindex--;}return true;}// 回溯三部曲:// 参数:字符串s以及记录当前截取子串的起始位置startindex(从同一个集合中连续截取,因此需要startindex用于递归纵向遍历)void backtracking(string s, int startindex) {// 终止条件,startindex超过s长度if (startindex == s.size()) { // 左闭,相等即超过// startindex能到最后,说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)results.push_back(path);return;}// for循环找到回文子串[startindex, i]for (int i = startindex; i < s.size(); i++) {// 是回文子串则截取并递归后面的子串,否则往后遍历找回文子串if (isPalindrome(s, startindex, i)) {// 截取子串并存储path.push_back(s.substr(startindex, i - startindex + 1)); // 注意substr的参数是起始位置以及截取长度backtracking(s, i + 1); // 从i之后的子串递归[i+1, s.size()-1]// 回溯,弹出path.pop_back(); // 之后for向右遍历,尝试截取[startindex, i+1]子串}}}};

复杂度

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

思路总结

思路完全参考代码随想录

  • 本题实际上算是困难题目
  • 难点有以下:
    • 将切割问题抽象为组合问题,并转换为树状结构
    • 如何模拟那些切割线(如何记录截取子串的始末位置)
    • 切割问题中递归如何终止(终止条件)
    • 在递归循环中如何截取子串(什么时候该递归,什么时候跳过)
    • 如何判断回文
  • 将切割问题抽象为组合问题,并转换为树状结构:
    • 例如对于字符串abcdef:
      组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
      切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。

    • 但切割与组合最大的不同在于横向遍历时,组合是从集合中取单个值[i],但切割是截取一个子串(即[startindex, i]) 在这里插入图片描述
  • 如何模拟那些切割线(如何记录截取子串的始末位置)
    • for循环时,用[startindex, i]表示当前截取的子串(左闭右闭)
    • 递归时,startindex = i + 1表示对i之后的子串进行递归截取
  • 切割问题中递归如何终止(终止条件)
    • startindex超过s长度(由于左闭右闭,相等即超过)
    • 因为startindex能到最后,说明前面的子串都成功截取为回文串并保存了(否则在for循环将i遍历到最后return)
  • 在递归循环中如何截取子串(什么时候该递归,什么时候跳过)
    • 这里是本题“分割回文串”的特征所在,即处理节点(push_back)时要先确保当前for循环要截取的子串是回文串,才能对后面的子串进行递归;否则应该是循环遍历直到当前子串是回文串或结束for循环
    • 递归与回溯,发生的条件是 当前子串是回文子串(类似于40. 组合总和 II中只有满足“当前取的值不重复”的条件才能递归是一样的。所以也可以写成
      for(...) {// 不是回文串则跳过if (!isPalindrome(...)) {continue;}// 递归与回溯...
      }
      
  • 如何判断回文子串:
    • 双指针法, 一个从头往后,一个从尾往前,对应相等则为回文串
  • TODO:动态规划优化判断回文子串

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

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

相关文章

常量和C预处理器

本文参考C Primer Plus第四章 文章目录 符号常量printf()函数和scanf()函数 printf()函数使用printf()printf()的转换说明修饰符 1.符号常量 C头文件limits.h和float.h分别提供了与整数类型和浮点类型大小限制相关的详细信息。头文件都定义了一系列供实现使用的符号常量。例如&…

腾讯云幻兽帕鲁4核16G14M服务器性能测评和价格

腾讯云幻兽帕鲁服务器4核16G14M配置&#xff0c;14M公网带宽&#xff0c;限制2500GB月流量&#xff0c;系统盘为220GB SSD盘&#xff0c;优惠价格66元1个月&#xff0c;277元3个月&#xff0c;支持4到8个玩家畅玩&#xff0c;地域可选择上海/北京/成都/南京/广州&#xff0c;腾…

网络安全02--负载均衡下的webshell连接

目录 一、环境准备 1.1ubentu虚拟机一台&#xff0c;docker环境&#xff0c;蚁剑 1.2环境压缩包&#xff08;文件已上传资源&#xff09;&#xff1a; 二、开始复原 2.1上传ubentu&#xff1a; 2.2解压缩 2.3版本20没有docker-compose手动下载&#xff0c;包已上传资源 …

uniapp复选框 实现排他选项

选择了排他选项之后 复选框其他选项不可以选择 <view class"reportData" v-for"(val, index) in obj" :key"index"> <view v-if"val.type 3" ><u-checkbox-group v-model"optionValue" placement"colu…

物联网协议Coap之C#基于Mozi的CoapClient调用解析

目录 前言 一、CoapClient相关类介绍 1、CoapClient类图 2、CoapClient的设计与实现 3、SendMessage解析 二、Client调用分析 1、创建CoapClient对象 2、实际发送请求 3、Server端请求响应 4、控制器寻址 总结 前言 在之前的博客内容中&#xff0c;关于在ASP.Net Co…

MongoDB实战

1.MongoDB介绍 1.1 什么是MongoDB MongoDB是一个文档数据库&#xff08;以JSON 为数据模型&#xff09;&#xff0c;由C语言编写&#xff0c;旨在为WEB应用提供可扩展的高性能数据存储解决方案。 文档来自于"JSON Document"&#xff0c;并非我们一般理解的 PDF&…

以太网交换基础VLAN原理与配置

目录 7.以太网交换基础 7.1.以太网协议 7.2.以太网帧介绍 7.3.以太网交换机 7.4.同网段数据通信全过程 8.VLAN原理与配置 8.1.VLAN的基本概念 8.2.VLAN的应用 7.以太网交换基础 7.1.以太网协议 以太网是当今现有局域网(Local Area Network,LAN)采用的最通用的通信协议…

数据结构排序小结

排序类型小结 &#x1f4a6; 插入排序直接插入排序希尔排序 &#x1f4a6; 选择排序直接选择排序堆排序 &#x1f4a6; 交换排序冒泡排序快速排序&#x1f43e;霍尔版本补坑位版本前后指针版本非递归版本 &#x1f4a6; 归并排序递归版本非递归版本 &#x1f4a6; 性能测试 &am…

DDPM的一点笔记

1 Title Denoising Diffusion Probabilistic Models&#xff08;Jonathan Ho、Ajay Jain、Pieter Abbeel&#xff09; 2 Conclusion This paper present high quality image synthesis results using diffusion probabilistic models, a class of latent variable models insp…

利用nginx宝塔免费防火墙实现禁止国外IP访问网站

本章教程&#xff0c;主要介绍&#xff0c;如何利用nginx宝塔面板中的插件免费防火墙&#xff0c;实现一键禁止国外IP访问网站。 目录 一、安装宝塔插件 二、 开启防火墙 一、安装宝塔插件 在宝塔面板中的软件商店&#xff0c;搜索防火墙关键词&#xff0c;找到Nginx免费防火…

java日志框架总结(三 、Log4j日志框架)

一、简介 Log4j ( Logger For Java ) , Java 日志的记录包。 官方网站 。Log4j 是 Apache 的一个开源项目&#xff0c; 为Java提供了日志记录功能。能够让程序员非常方便的记录日志&#xff0c; 并且提供了多种适配方式&#xff0c;能满足各种需求。 使用Log4j 只需要导入一个…

第四篇:怎么写express的路由(接口+请求)

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 &#x1f4d8; 引言&#xff1a; &#x1f4…

python在线聊天室(带聊天保存)

python Socket在线聊天室(带聊天保存) 需求功能 1.聊天信息保存功能(服务端会把信息保存到一个txt里面) 2.使用pyqt5框架作为一个可视化界面 3.具备一个服务端和多个客户端的功能 4.具备离线加入黑名单(离线踢出) 5.具备在线加入黑名单(在线加入黑名单被踢出) 6.具备群聊功能…

无际线复选框

效果演示 实现了一个网格布局&#xff0c;其中每个网格是一个复选框&#xff0c;可以选择是否显示。每个复选框都有一个漂浮的天花板&#xff0c;表示它是一个房间的天花板。每个房间的天花板都有一个不同的形状和颜色&#xff0c;分别对应不同的房间。整个页面的背景是一个由两…

0127-2-Vue深入学习5—Vue-Router路由模式

1、Vue-Router三种路由模式&#xff1a; hash&#xff1a;#️⃣使用URL hash 值来做路由&#xff0c;支持所有路由器&#xff1b;history:&#x1f4d6;依赖HTML5 History API和服务器配置&#xff1b;abstract:⛓支持所有JS运行环境&#xff0c;Node.js服务端&#xff1b; 1.1…

安全防御{第三次作业(在第二次作业上添加点需求)}

目录 需求&#xff1a; 拓扑图&#xff1a; 注意&#xff1a;先打开防火墙web界面&#xff0c;在此不做演示 1.要求一&#xff1a;&#xff0c;生产区在工作时间内可以访问服务器区&#xff0c;仅可以访问http服务器 2.要求二&#xff1a;办公区全天可以访问服务器区&#…

使用一个定时器(timer_fd)管理多个定时事件

使用一个定时器(timer_fd)管理多个定时事件 使用 timerfd_xxx 系列函数可以很方便的与 select、poll、epoll 等IO复用函数相结合&#xff0c;实现基于事件的定时器功能。大体上有两种实现思路&#xff1a; 为每个定时事件创建一个 timer_fd&#xff0c;绑定对应的定时回调函数…

考研C语言刷题基础篇之分支循环结构基础(二)

目录 第一题分数求和 第二题&#xff1a;求10 个整数中最大值 第三题&#xff1a;在屏幕上输出9*9乘法口诀表 第四题&#xff1a;写一个代码&#xff1a;打印100~200之间的素数 第五题&#xff1a;求斐波那契数的第N个数 斐波那契数的概念&#xff1a;前两个数相加等于第三…

Objective-C方法的声明实现及调用

1.无参数的方法 1)声明 a.位置&#xff1a;在interface括弧的外面 b.语法&#xff1a; - (返回值类型)方法名称; interface Person : NSObject -(void) run; end 2)实现 a.位置&#xff1a;在implementation中实现 b.语法&#xff1a;加大括弧将方法实现的代码写在大括孤之中 …

Unity Mask合批情况验证

1.首先是两个Mask完全重合的情况下 每张图片使用的image都来自同一个图集 发现彼此之间是没有合批的&#xff0c;但是每个Mask内部是实现了合批的 经过计算此种情况的visiableList&#xff1a;mask1&#xff0c;IM1&#xff0c;IM2&#xff0c;mask2&#xff0c;IM3&#xf…