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

力扣日记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:动态规划优化判断回文子串

相关文章:

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

力扣日记&#xff1a;【回溯算法篇】131. 分割回文串 日期&#xff1a;2023.1.27 参考&#xff1a;代码随想录、力扣 131. 分割回文串 题目描述 难度&#xff1a;中等 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可…...

如何用web界面打开华为防火墙

目录 1.创建一个虚拟网卡 2.cloud操作 3.防火墙上操作 4. 登录 1.创建一个虚拟网卡 2.cloud操作 3.防火墙上操作 4. 登录...

力扣20、有效的括号(简单)

1 题目描述 图1 题目描述 2 题目解读 给定的字符串只包含括号&#xff0c;判断这个字符串中的括号是否按照正确顺序出现&#xff0c;即这个字符串是否有效。 3 解法一&#xff1a;栈 C的STL中的stack&#xff0c;在解题时非常好用。 3.1 解题思路 使用栈stk&#xff0c;并枚举…...

Android 系统启动过程

当按下电源时&#xff0c;引导芯片代码会从预定义的地方(固化在ROM) 开始执行,加载引导程序BootLoader到RAM,然后执行。 启动内核的第一个进程idle(pid0),idle进程是Linux系统第一个进程&#xff0c;是init进程和kthreadd进程的父进程。 idle的主要作用 初始化进程以及内存管…...

基于STM32的智能手环设计与实现

需要原理图工程&#xff0c;源码&#xff0c;PCB工程的朋友收藏&#xff0c;这篇文章关注我&#xff0c;私我吧&#xff01;&#xff01;&#xff01; 基于STM32的智能手环设计与实现 摘要一、研究背景及意义二、实现功能三、系统方案设计系统方案设计框图3.1 单片机芯片选择3…...

[BJDCTF2020]The mystery of ip

hint 猜测ip和XFF有关 加一个XFF 下面这一步是看了wp出来的&#xff1a;存在ssti 这里尝试用jinja的注入方法&#xff0c;页面回显了是php的smarty框架 查了一下smarty的注入方法&#xff0c;发现可以直接执行php命令 在根目录找到flag...

RUST笔记:candle使用基础

candle介绍 candle是huggingface开源的Rust的极简 ML 框架。 candle-矩阵乘法示例 cargo new myapp cd myapp cargo add --git https://github.com/huggingface/candle.git candle-core cargo build # 测试&#xff0c;或执行 cargo ckeckmain.rs use candle_core::{Device…...

Python算法题集_接雨水

本文为Python算法题集之一的代码示例 题目42&#xff1a;接雨水 说明&#xff1a;给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]…...

FIND_IN_SET的使用:mysql表数据多角色、多用户查询

MySQL 函数 FIND_IN_SET 是用于在逗号分隔的字符串中查找特定值的函数。它的语法如下&#xff1a; FIND_IN_SET(search_value, comma_separated_string)search_value 是要查找的值。 comma_separated_string 是逗号分隔的字符串&#xff0c;在这个字符串中查找指定的值。FIND_…...

JVM篇----第十一篇

系列文章目录 文章目录 系列文章目录前言一、在新生代-复制算法二、在老年代-标记整理算法三、分区收集算法四、GC 垃圾收集器前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你…...

鸿蒙HarmonyOS获取GPS精确位置信息

参考官方文档 #1.初始化时获取经纬度信息 aboutToAppear() {this.getLocation() } async getLocation () {try {const result await geoLocationManager.getCurrentLocation()AlertDialog.show({message: JSON.stringify(result)})}catch (error) {AlertDialog.show({message…...

java正则校验,手机号,邮箱,日期格式,时间格式,数字金额两位小数

java正则校验&#xff0c;手机号&#xff0c;邮箱&#xff0c;日期格式&#xff0c;时间格式&#xff0c;数字金额两位小数 3.58是否为金额&#xff1a;true 3.582是否为金额&#xff1a;false 1284789qq.com是否为email&#xff1a;true 1284789qq.com是否为email&#xff1…...

php下curl发送cookie

目录 一&#xff1a;使用 CURLOPT_COOKIE 选项 二&#xff1a;CURLOPT_COOKIEFILE 三&#xff1a;CURLOPT_HTTPHEADER php curl发送cookie的几种方式,下面来介绍下 一&#xff1a;使用 CURLOPT_COOKIE 选项 通过设置 CURLOPT_COOKIE 选项&#xff0c;你可以将 cookie 字符…...

stable diffusion学习笔记——文生图(一)

模型设置 基本模型 基本模型也就是常说的checkpoint&#xff08;大模型&#xff09;&#xff0c;基本模型决定了生成图片的主体风格。 如上图所示&#xff0c;基本模型的后缀为.safetensors。需要存放在特定的文件夹下。 如果用的是启动器&#xff0c;可以在启动器内直接下载。…...

Linux下安装openresty

Linux下安装openresty 十一、Linux下安装openresty11.1.概述11.2.下载OpenResty并安装相关依赖&#xff1a;11.3.使用wget下载:11.4.解压缩:11.5.进入OpenResty目录:11.6.编译和安装11.7.进入OpenResty的目录&#xff0c;找到nginx&#xff1a;11.8.在conf目录下的nginx.conf添…...

【IM】如何保证消息可用性(一)

目录 1. 基本概念1.1 长连接 和 短连接1.2 PUSH模式和PULL模式 2. 背景介绍2.1 理解端到端的思想 3. 方案选型3.1 技术挑战3.2 技术目标 1. 基本概念 在讲解消息可用性之前&#xff0c;需要理解几个通信领域的基本概念。 1.1 长连接 和 短连接 什么是长连接&#xff0c;短连接…...

js直接下载附件和通过blob数据类型下载文件

js下载文件方式有使用a标签的&#xff0c;也有直接用window.open的&#xff0c;还有用form表单的&#xff1b;这里采用的是a标签的下载方式&#xff0c;一种是url直接下载&#xff0c;另一种是文件的blob数据类型进行下载。 文件blob数据类型的获取一般是后端返回文件的二进制流…...

第2章-神经网络的数学基础——python深度学习

第2章 神经网络的数学基础 2.1 初识神经网络 我们来看一个具体的神经网络示例&#xff0c;使用 Python 的 Keras 库 来学习手写数字分类。 我们这里要解决的问题是&#xff0c; 将手写数字的灰度图像&#xff08;28 像素28 像素&#xff09;划分到 10 个类别 中&#xff08;0…...

【Docker】Docker学习⑧ - Docker仓库之分布式Harbor

【Docker】Docker学习⑧ - Docker仓库之分布式Harbor 一、Docker简介二、Docker安装及基础命令介绍三、Docker镜像管理四、Docker镜像与制作五、Docker数据管理六、网络部分七、Docker仓库之单机Dokcer Registry八、 Docker仓库之分布式Harbor1 Harbor功能官方介绍2 安装Harbor…...

一行命令在 wsl-ubuntu 中使用 Docker 启动 Windows

在 wsl-ubuntu 中使用 Docker 启动 Windows 0. 背景1. 验证我的系统是否支持 KVM&#xff1f;2. 使用 Docker 启动 Windows3. 访问 Docker 启动的 Windows4. Docker Hub 地址5. Github 地址 0. 背景 我们可以在 Windows 系统使用安装 wsl-ubuntu&#xff0c;今天玩玩在 wsl-ub…...

如何用League-Toolkit提升30%游戏决策效率?完整指南

如何用League-Toolkit提升30%游戏决策效率&#xff1f;完整指南 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 价值定位&#xf…...

基于圣女司幼幽-造相Z-Turbo的Java面试题智能生成与解析实战

基于圣女司幼幽-造相Z-Turbo的Java面试题智能生成与解析实战 最近在帮团队招聘Java工程师&#xff0c;一个很深的感触是&#xff1a;准备面试题太费劲了。不同岗位&#xff08;比如后端开发和大数据开发&#xff09;需要的技术栈侧重点完全不同&#xff0c;网上找的题目要么太…...

FlowState Lab跨周期波动模式提取效果:从秒级到年度的规律发现

FlowState Lab跨周期波动模式提取效果&#xff1a;从秒级到年度的规律发现 1. 时间序列分析的革命性突破 时间序列分析领域最近迎来了一项重要突破。传统方法往往只能聚焦单一时间尺度&#xff0c;要么分析高频交易数据&#xff0c;要么研究季节性规律&#xff0c;很难同时捕…...

双冗余链路实现(2/2期)

目录 拓扑&#xff1a; 基础需求&#xff1a; 出口路由器&#xff08;双路&#xff09;&#xff1a; 静态路由&#xff1a; 防火墙配置&#xff1a; 全区域互通透传&#xff1a; 静态路由&#xff1a; 冗余备份&#xff1a; 核心交换机&#xff1a; 静态路由&#xff…...

3个变革性步骤:用163MusicLyrics彻底解决歌词获取难题

3个变革性步骤&#xff1a;用163MusicLyrics彻底解决歌词获取难题 【免费下载链接】163MusicLyrics Windows 云音乐歌词获取【网易云、QQ音乐】 项目地址: https://gitcode.com/GitHub_Trending/16/163MusicLyrics 在数字化音乐时代&#xff0c;歌词已不再是简单的文字附…...

应对维普AIGC史诗级升级:2026降重急救包!5款工具基准测试 x 4大手改重构技巧

论文初稿快要交了&#xff0c;维普却突然搞了个大动作&#xff0c;把系统给升级了。说实话&#xff0c;这事真挺让人头疼的&#xff0c;有人前两天查还是绿的&#xff0c;以为稳了&#xff0c;结果升级完再一测&#xff0c;AI率直接飙红。 但别慌&#xff0c;也别怀疑自己是不…...

如何快速掌握AI变声神器RVC:面向初学者的完整指南

如何快速掌握AI变声神器RVC&#xff1a;面向初学者的完整指南 【免费下载链接】Retrieval-based-Voice-Conversion-WebUI 语音数据小于等于10分钟也可以用来训练一个优秀的变声模型&#xff01; 项目地址: https://gitcode.com/GitHub_Trending/re/Retrieval-based-Voice-Con…...

零基础掌握开源工具:3步实现群晖Photos功能强化

零基础掌握开源工具&#xff1a;3步实现群晖Photos功能强化 【免费下载链接】Synology_Photos_Face_Patch Synology Photos Facial Recognition Patch 项目地址: https://gitcode.com/gh_mirrors/sy/Synology_Photos_Face_Patch 当你面对海量照片却无法享受智能分类的便…...

手把手教你用FreeRTOS创建第一个任务:从栈初始化到SVC调用的完整流程

深入解析FreeRTOS任务启动机制&#xff1a;从栈初始化到任务切换的实战指南 在嵌入式开发领域&#xff0c;实时操作系统(RTOS)已成为复杂项目的标配工具。作为开源RTOS中的佼佼者&#xff0c;FreeRTOS凭借其轻量级、可移植性强等特点&#xff0c;在STM32等Cortex-M系列MCU上广…...

高效获取Sketchfab 3D资源:Firefox专属下载工具使用指南

高效获取Sketchfab 3D资源&#xff1a;Firefox专属下载工具使用指南 【免费下载链接】sketchfab sketchfab download userscipt for Tampermonkey by firefox only 项目地址: https://gitcode.com/gh_mirrors/sk/sketchfab 在3D设计与开发领域&#xff0c;获取高质量模型…...