Day66 代码随想录打卡|回溯算法篇---分割回文串

题目(leecode T131):

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

方法:本题是一个分割回文串的问题,是回溯算法的另一类问题。 针对一个字符串,我们要对其进行分割,并且确保分割后生成的子串也必须全都是回文串。分析回溯三部曲

1:传入参数与返回值:传入字符串s,以及切割的起始位置startIndex,不需要返回值

2:终止条件:因为切割位置startIndex控制的是切割的起始位置,当startIndex大于等于s.size时,就意味着已经切到了最后,也就该停止了。

3:单层处理逻辑:在单层中我们需要从字符串中截取子串。

for (int i = startIndex; i < s.size(); i++)循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文,如果是回文,就加入在vector<string> path中,path用来记录切割过的回文子串。

题解:
 

class Solution {
private:
    vector<string> path;
    vector<vector<string>> result;
    void backtracking(const string& s,int startIndex){
        if(startIndex >= s.size()){             //终止条件
            result.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);
            }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) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

溶解氧(DO)理论指南(3)

转载自梅特勒官网资料&#xff0c;仅用于学习交流&#xff0c;侵权则删&#xff01; 溶解氧理论指南 设备操作3.1 DO电极准备3.2 DO电极校准3.3 进行DO测量3.4 转换单位3.5 维护和储存 设备操作 本章总结了 DO电极日常使用的一些建议。它们基于普遍接受的操作规则。 3.1 DO电…

如何在玩客云中安装小雅AList并实现使用手机平板远程连接听歌看电影

文章目录 前言1. 本地部署AList2. AList挂载网盘3. 部署小雅alist3.1 Token获取3.2 部署小雅3.3 挂载小雅alist到AList中 4. Cpolar内网穿透安装5. 创建公网地址6. 配置固定公网地址 前言 本文主要介绍如何在安装了CasaOS的玩客云主机中部署小雅AList&#xff0c;并在AList中挂…

构建高精度室内定位导航系统,从3DGIS到AI路径规划的全面解析

室内定位导航系统是一种利用多种技术实现室内精准定位和导航的智能系统&#xff0c;即便没有卫星信号&#xff0c;也能实现精准导航。维小帮室内定位导航系统是基于自研的地图引擎与先进定位技术&#xff0c;结合智能路径规划算法&#xff0c;解决了人们在大型复杂室内场所最后…

搜维尔科技:【研究】Scalefit是一款可在工作场所自动处理3D姿势分析结果的软件

Scalefit是一款可在工作场所自动处理 3D 姿势分析结果的软件。这甚至可以在衡量员工的同时发生。然后&#xff0c;Scalefit 根据国际标准对姿势、压缩力和关节力矩进行分析和可视化。 3D姿势分析 如今&#xff0c;Xsens 技术可让您快速测量工作场所员工的态度。一套带有 17 个…

【笔记】centos7虚拟机连接dbeaver数据库失败好多次折磨我三天三夜

终于在第四个方法连接上了 你知道这四天三夜我怎么过来的吗 真的好痛苦 一个问题延申了无数个问题到最后我都不记得自己在解决什么问题 Access denied for user xiaoming192.168.81.1 (using password: YES) Public Key Retrieval is not allowed &#xff08;一&#xff09;跳…

高中数学:立体几何-基本立体图形分类

一、常见空间几何体 二、多面体 1、棱柱 2、棱锥 3、棱台 4、相关关系 三、旋转体 1、圆柱 2、圆锥 3、圆台 4、球

新一代iPhone成传家宝,这升级给我看呆了

6 月刚过&#xff0c;数码圈就迎来了平淡期&#xff0c;虽然各家手机层出不穷&#xff0c;但也只是新瓶装旧酒&#xff0c;没啥新意。 翘首以盼的新机也得等到 9 月份才会遍地开花。 这其中让人备受期待的肯定有苹果的一票&#xff0c;而最近苹果新机的消息也渐渐浮出水面了。…

Linux之免费证书工具certbot安装和使用

一、cerbot简介 Certbot是一个免费的开源软件工具&#xff0c;用于在手动管理的网站上自动使用Let’s Encrypt证书以启用HTTPS。要想让自己的网站启用https协议&#xff0c;需要一个由CA&#xff08;数字证书认证机构&#xff09;颁发的&#xff0c;能够让各个浏览器都能承认的…

AIGC在创意设计中的应用

随着人工智能技术的不断进步&#xff0c;AIGC&#xff08;人工智能生成内容&#xff09;已成为创意设计领域的新宠。这种新兴技术以其强大的创作能力和高效的工作效率&#xff0c;正逐渐改变着设计师们的工作方式和创作流程。在这个变革的时代&#xff0c;设计师们纷纷拥抱AIGC…

英伟达今年在华销售额预计将达120亿美元、MiniMax创始人:三年后才会出现“杀手级”AI应用

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 更多资源欢迎关注 1、英伟达今年在华销售额预计将达120亿美元 芯片咨询公司SemiAnalysis报告预估&#xff0c;今年英伟达有望在中国销售价值约120亿美元的人工智能芯片。黄仁勋曾表示&#xff0c;希望借助新的芯片使得…

树链剖分相关

树链剖分这玩意儿还挺重要的&#xff0c;是解决静态树问题的一个很好的工具~ 这里主要介绍一下做题时经常遇到的两个操作&#xff1a; 1.在线求LCA int LCA(int x,int y){while(top[x]!top[y])if(dep[top[x]]>dep[top[y]]) xfa[top[x]];else yfa[top[y]];return dep[x]&l…

cdn中配置ssl证书

##red## &#x1f534; 大家好&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff0c;雄雄的小课堂。 SSL KEY 这个里面放的是&#xff1a;private.pem文件中的内容 SSL PEM 这个里面放的是&#xff1a;fullchain.crt文件中的内容&#xff0c;注意&#xff0c;这个…

JavaSE 面向对象程序设计进阶 IO流 字节流详解 抛出异常

input output 像水流一样读取数据 存储和读取数据的解决方案 内存中数据不能永久化存储 程序停止运行 数据消失 File只能对文件本身进行操作 不能读写文件里存储的数据 读写数据必须要有IO流 可以把程序中的数据保存到文件当中 还可以把本地文件中的数据读取到数据当中 分…

初学SpringMVC之 RestFul 风格、重定向和转发

RestFul 风格改变 URL 形式 比如之前是&#xff1a;http://localhost:8080/add?a1&b2 现在是&#xff1a;http://localhost:8080/add/a/b&#xff08;全是斜杠&#xff09; package com.demo.controller;import org.springframework.stereotype.Controller; import org…

ChatTTS的爆火是必然,它正在重新定义我们与机器对话的方式

当AI技术与语音合成相遇&#xff0c;开源技术众多&#xff0c;为什么 ChatTTS 能够一夜爆火&#xff1f;你有听说过能说情感真切文字的 AI 吗&#xff1f; 前言 想象一下&#xff0c;你只需输入一句话&#xff0c;AI就能念得声情并茂&#xff0c;不仅支持中英文混读&#xff0…

Webpack安装以及快速入门

3 Webpack 1 什么是Webpack https://webpack.js.org/ (官网) webpack 是一个现代 javascript 应用程序的 静态模块打包器 (module bundler) 待会要学的 vue-cli 脚手架环境, 集成了 webpack, 所以才能对各类文件进行打包处理 webpack是一个 静态模块 打包器,可以做以下的这…

一文彻底搞懂性能测试

性能测试概念 我们经常看到的性能测试概念&#xff0c;有人或称之为性能策略&#xff0c;或称之为性能方法&#xff0c;或称之为性能场景分类&#xff0c;大概可以看到性能测试、负载测试、压力测试、强度测试等一堆专有名词的解释。 针对这些概念&#xff0c;我不知道你看到的…

牛刀小试--下三角对称矩阵压缩存储

解析博客: 矩阵存储和特殊矩阵的压缩存储_n阶对称矩阵压缩-CSDN博客 函数功能: //为N阶下三角矩阵初始化成的一维数组分配空间 void Init_triangular_matrix(int *&matrix); //返回二维下三角矩阵的值(压缩存取) int get_Value_triangular_matrix(int matrix[],int x,int …

Canvas:实现在线画板操作

想象一下&#xff0c;用几行代码就能创造出如此逼真的图像和动画&#xff0c;仿佛将艺术与科技完美融合&#xff0c;前端开发的Canvas技术正是这个数字化时代中最具魔力的一环&#xff0c;它不仅仅是网页的一部分&#xff0c;更是一个无限创意的画布&#xff0c;一个让你的想象…

谷粒商城学习笔记-22-分布式组件-SpringCloud-OpenFeign测试远程调用

文章目录 一&#xff0c;OpenFeign的简介二&#xff0c;OpenFeign的使用步骤1&#xff0c;场景说明2&#xff0c;引入依赖2&#xff0c;开启OpenFeign3&#xff0c;编写Feign接口4&#xff0c;使用feign调用远程接口5&#xff0c;验证 错误记录 上一节学习了注册中心&#xff0…