当前位置: 首页 > 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;或者需要其他什么曲折的方式…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...