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

【算法与数据结构】131、LeetCode分割回文串

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:本题仍然使用回溯算法的一般结构。加入了一个判断是否是回文串的函数,利用起始和终止索引进行判断,字符串使用引用输入, 减少传参的时间开销。将开始索引大于等于字符串长度作为终止条件,表示已经找到一个回文串的组合。此外,进一步改进算法的性能,可以建立一个查找数组,提前算出分割的子串是否为回文串,使用时直接判断即可。

在这里插入图片描述

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

  程序如下

class Solution {
private:vector<vector<string>> result;vector<string> path;bool isSymmetry(const string& s, const int start, const int end) {bool flag = true;for (int i = start, j = end; i <= j; i++, j--) {if (s[i] != s[j]) {flag = false;break;}}return flag;}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 (isSymmetry(s, startIndex, i)) {	// 是回文串才加入结果数组string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);}else {	// 不是回文串跳过continue;}backtracking(s, i + 1);path.pop_back();}}
public:vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};

复杂度分析:

  • 时间复杂度: O ( n ∗ 2 n ) O(n*2^n) O(n2n), n代表字符串长度。
  • 空间复杂度: O ( n 2 ) O(n^2) O(n2)

三、完整代码

# include <iostream>
# include <string>
# include <vector>
using namespace std;class Solution {
private:vector<vector<string>> result;vector<string> path;bool isSymmetry(const string& s, const int start, const int end) {bool flag = true;for (int i = start, j = end; i <= j; i++, j--) {if (s[i] != s[j]) {flag = false;break;}}return flag;}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 (isSymmetry(s, startIndex, i)) {	// 是回文串才加入结果数组string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);}else {	// 不是回文串跳过continue;}backtracking(s, i + 1);path.pop_back();}}
public:vector<vector<string>> partition(string s) {backtracking(s, 0);return result;}
};int main() {string s = "aab";Solution s1;vector<vector<string>> result = s1.partition(s);for (vector<vector<string>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<string>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}

end

相关文章:

【算法与数据结构】131、LeetCode分割回文串

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;本题仍然使用回溯算法的一般结构。加入了一个判断是否是回文串的函数&#xff0c;利用起始和终止索引进…...

网络编程学习笔记

参考&#xff1a; 套接字通信部分 《TCP/IP 网络编程》以及《TCP/IP网络编程》学习笔记 socket 编程 1. 字节序 字节序&#xff0c;顾名思义字节的顺序&#xff0c;就是大于一个字节类型的数据在内存中的存放顺序&#xff0c;也就是说对于单字符来说是没有字节序问题的&…...

腾讯待办停运后怎么办呢?导出的ics文件怎么打开查看

待办类工具在日常工作中的应用是比较广泛的&#xff0c;很多人会选择使用待办软件记录备忘事项&#xff0c;其中一些提醒类的工具是比较广泛使用的。腾讯待办属于一款待办事项和日程管理工具&#xff0c;它通常是以微信小程序的形式&#xff0c;为大家提供时间管理规划&#xf…...

家长群如何发成绩?

老师们是否经常被家长们追问&#xff1a;“老师&#xff0c;我孩子的成绩出来了吗&#xff1f;”、“老师&#xff0c;我孩子考了多少分&#xff1f;”等等。要想解决这个问题&#xff0c;看完这篇文章你就可以让家长们能够自助查询孩子的成绩了。 一、什么是成绩查询系统&…...

数组区域检索的优化 --- 分块,线段树,树状数组

思考 首先让我们来思考一个问题&#xff0c;给定一个数组&#xff0c;和left与right的值&#xff0c;让你求这个数组中left到right之间元素的和&#xff0c;你会怎么计算&#xff1f;最简单的当然是遍历。如果有人问你这个问题的时候&#xff0c;他决对是会让你优化的&#xff…...

若依侧边栏添加计数标记效果

2023.11.13今天我学习了如何对若依的侧边栏添加技术标记的效果&#xff0c;如图&#xff1a; 我们需要用到两个页面&#xff1a; 先说子组件实现计数标记效果 1.item.vue <script> export default {name: MenuItem,functional: true,props: {icon: {type: String,defau…...

WebSocket技术解析:实现Web实时双向通信的利器

当今互联网的发展中&#xff0c;实时性成为了越来越重要的需求&#xff0c;特别是在Web应用程序中。传统的HTTP协议在处理实时性方面存在一些局限性&#xff0c;因此WebSocket技术的出现填补了这一空白。WebSocket是一种在单个TCP连接上进行全双工通信的协议&#xff0c;它允许…...

深圳联强优创手持PDA身份证阅读器 身份证核验手持机

身份证手持机外观比较小巧&#xff0c;方便携带&#xff0c;支持条码识别、人脸识别、NFC卡刷卡、内置二代证加密模块&#xff0c;可离线采集和识别二代身份证&#xff0c;进行身份识别。信息读取更便捷、安全高效。采用IP65高防护等级&#xff0c;1.5M防摔&#xff0c;可以适应…...

力扣labuladong——一刷day31

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣226. 翻转二叉树二、力扣116. 填充每个节点的下一个右侧节点指针三、力扣114. 二叉树展开为链表 二叉树解题的思维模式分两类&#xff1a; 1、是否可以…...

里氏代换原则

package com.jmj.principles.dmeo2.after;/*** 四边形接口*/ public interface Quadrilateral {double getLength();double getWidth();}package com.jmj.principles.dmeo2.after;/*** 长方形类*/ public class Rectangle implements Quadrilateral{private double length;priv…...

Illumination Adaptive Transformer

Abstract. 现实世界中具有挑战性的照明条件&#xff08;低光、曝光不足和曝光过度&#xff09;不仅会产生令人不快的视觉外观&#xff0c;还会影响计算机视觉任务。现有的光自适应方法通常单独处理每种情况。更重要的是&#xff0c;它们中的大多数经常在 RAW 图像上运行或过度…...

【教3妹学编程-算法题】给小朋友们分糖果 II

3妹&#xff1a;1 8得8&#xff0c;2 816&#xff0c; 3 8妇女节… 2哥 : 3妹&#xff0c;在干嘛呢 3妹&#xff1a;双11不是过了嘛&#xff0c; 我看看我这个双十一买了多少钱&#xff0c; 省了多少钱。 2哥 : 我可是一分钱没买。 3妹&#xff1a;我买了不少东西&#xff0c; …...

应急响应练习2

目录 1. 请提交攻击者的ip与系统版本 2. 攻击者通过某个组件漏洞获得服务器权限&#xff0c;请提交该组件的名称 3. 请提交攻击者首次攻击成功的时间 4. 请提交攻击者上传的webshell文件绝对路径 5. 请提交攻击者使用的webshell管理工具 6. 攻击者进一步留下的免杀的webs…...

JS算法练习 11.13

leetcode 2625 扁平化嵌套数组 请你编写一个函数&#xff0c;它接收一个 多维数组 arr 和它的深度 n &#xff0c;并返回该数组的 扁平化 后的结果。 多维数组 是一种包含整数或其他 多维数组 的递归数据结构。 数组 扁平化 是对数组的一种操作&#xff0c;定义是将原数组部…...

js升序排序

function sortByKey(array, key) {return array.sort(function(a, b) {var x Number(a[key]);var y Number(b[key]);return x < y ? -1 : x > y ? 1 : 0; //或者 return x-y});}...

2023亚太杯数学建模C题思路

文章目录 0 赛题思路1 竞赛信息2 竞赛时间3 建模常见问题类型3.1 分类问题3.2 优化问题3.3 预测问题3.4 评价问题 4 建模资料5 最后 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 竞赛信息 2023年第十三…...

【ArcGIS Pro微课1000例】0030:ArcGIS Pro中自带晕渲地貌工具的妙用

在ArcGIS中,制作地貌晕渲效果通常的做法是先制作山体阴影效果,然后叠加在DEM的下面,再改变DEM的透明度来实现。而在ArcGIS Pro中自带了效果显著的晕渲地貌工具。 文章目录 一、晕渲地貌工具1. 符号系统2. 栅格函数二、山体阴影效果1. 工具箱2. 栅格函数打开ArcGIS Pro3.0,加…...

【原创】java+swing+mysql办公用品管理系统设计与实现

摘要&#xff1a; 办公用品管理系统是一个设计和实现办公用品库存和使用管理的信息系统。此系统可以提高办公用品的利用率&#xff0c;减少浪费&#xff0c;使办公用品管理更加高效、规范、便捷。本文主要介绍使用javaswingmysql技术去开发实现一个办公用品管理系统。 功能分…...

sqlalchemy查询数据为空,查询范围对应的数据在数据库真实存在

记录一个开发过程遇到的小bug,构造些伪数据还原并解释。 """ 场景:传参触发了查询条件,数据库中是存在传参对应范围的数据,但是通过查询条件得到的查询结果为空 """ 入参场景一: start_time = "2023-11-13" end_time = "202…...

Code Former安装及使用

Code Former是南洋理工大学和商汤科技联合研究中心联合开发一款AI人脸修复算法&#xff0c;通过该算法&#xff0c;可以对已经模糊的图片进行人脸修复&#xff0c;找回斑驳的记忆 由于网上对于Code Former的封装&#xff0c;全都是要花钱&#xff0c;或者需要其他什么曲折的方式…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...

【技巧】dify前端源代码修改第一弹-增加tab页

回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码&#xff0c;在知识库增加一个tab页"HELLO WORLD"&#xff0c;完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...

简约商务通用宣传年终总结12套PPT模版分享

IOS风格企业宣传PPT模版&#xff0c;年终工作总结PPT模版&#xff0c;简约精致扁平化商务通用动画PPT模版&#xff0c;素雅商务PPT模版 简约商务通用宣传年终总结12套PPT模版分享:商务通用年终总结类PPT模版https://pan.quark.cn/s/ece1e252d7df...