【算法笔记】LCR 086. 分割回文串

在这里插入图片描述
基本思想是使用回溯法,回溯法都可以将问题划分为一个解空间树:假设字符串s为"aab",那么我们可以使用深度优先搜索去构建解空间树:
在这里插入图片描述
dfs遍历出来的第一个序列是[a, a, b],显然该序列都是回文子串,接着回溯,遍历下一个序列,为[a, ab],不是回文子串,去除…如此往下遍历,将符合要求的序列加入到结果集res中,直到遍历整个解空间树

此题的重要思想有两个:
Java中的List变量存储的是List的地址,而非List本身,因此可以构建一个path列表,用于存储当前已经遍历的序列,当dfs向下遍历的时候则将新遍历的字符串加入path中;当向上回溯的时候,可以将path中的最后一个元素remove掉,从而恢复到上一个遍历状态

class Solution {public List<String> path = new ArrayList<>();public List<List<String>> result = new ArrayList();public void f(String str, int start){if (start >= str.length()){// 防止深复制导致的将List地址存入result,需要新建Listresult.add(new ArrayList<>(path));}for (int i = start; i < str.length(); i++) {if (isPalindrome(str, start, i)){path.add(str.substring(start, i+1));}elsecontinue;f(str, i+1);path.remove(path.size()-1); // 回溯}}public boolean isPalindrome(String s,int start,int end){//start从左到右,end从右到左,判断前后是否一致for(int i=start,j=end;i<j;i++,j--){if(s.charAt(i)!=s.charAt(j)){return false;}}return true;}public String[][] partition(String s) {f(s, 0);int rows = result.size();String[][] ret = new String[rows][];for (int i = 0; i < rows; ++i) {int cols = result.get(i).size();ret[i] = new String[cols];for (int j = 0; j < cols; ++j) {ret[i][j] = result.get(i).get(j);}}return ret;}
}

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

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

相关文章

前后端分离项目-基于springboot+vue的足球青训俱乐部管理后台系统的设计与实现(内含代码+文档+报告)

博主介绍&#xff1a;✌全网粉丝10W,前互联网大厂软件研发、集结硕博英豪成立工作室。专注于计算机相关专业毕业设计项目实战6年之久&#xff0c;选择我们就是选择放心、选择安心毕业✌ &#x1f345;由于篇幅限制&#xff0c;想要获取完整文章或者源码&#xff0c;或者代做&am…

colab切换目录的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

【MySQL】深入理解MySQL中的Join算法

原创不易&#xff0c;注重版权。转载请注明原作者和原文链接 文章目录 什么是JoinIndex Nested-Loop JoinBlock Nested-Loop JoinMRR & BKA总结 在数据库处理中&#xff0c;Join操作是最基本且最重要的操作之一&#xff0c;它能将不同的表连接起来&#xff0c;实现对数据集…

前端八股文

目录 一、CSS1.说一下CSS的盒模型。2.CSS选择器的优先级&#xff1f;3.隐藏元素的方法有哪些&#xff1f;4.px和rem的区别是什么&#xff1f;5.重绘重排有什么区别&#xff1f;6.让一个元素水平垂直居中的方式有哪些&#xff1f;7.CSS的哪些属性哪些可以继承&#xff1f;哪些不…

vscode 调试使用 make 编译的项目

1、首先点击运行 --> 启动调试&#xff1a; 2、选择g或gcc生成和调试活动文件&#xff1a; 3、出现下面提示是正常的&#xff0c;点击仍要调试&#xff1a; 点击打开“launch.json”&#xff1a; 4、此时会在项目工作目录下生成tsak.josn和launch.json文件&#xff1a; 如…

Android rtmp 低延迟直播方案:简介

Android rtmp 低延迟直播方案:简介 Android RTMP 低延迟直播方案:使用 RTMP 推送至 ZLMediaKit,通过 WebRTC 进行拉流。

【eNSP】VLAN基础配置

一、基于接口划分VLAN&#xff08;Access接口和Trunk接口&#xff09; 1、创建VLAN LSW1 [LSW1]vlan batch 10 20 Info: This operation may take a few seconds. Please wait for a moment...done.LSW2 [LSW2]vlan batch 10 20 Info: This operation may take a few second…

【网络】UDP和TCP套接字编程

目录 一、初始ip地址和port二、网络字节序三、socket编程1、sockaddr结构2、socket编程接口2.1、创建 socket接口2.2、绑定端口号2.3、监听socket2.4、接收请求2.5、建立连接2.6、收消息2.7、发消息 3、UDP套接字编程 -- 现实大小写转换4、TCP套接字编程 -- 原生多线程现实TCP通…

若依微服务前后端部署启动流程(只记录)

若依官网&#xff1a;https://www.ruoyi.vip/ 若依源码下载&#xff0c;直接zip既可&#xff1a;RuoYi-Cloud: &#x1f389; 基于Spring Boot、Spring Cloud & Alibaba的分布式微服务架构权限管理系统&#xff0c;同时提供了 Vue3 的版本 下载解压&#xff0c;导入 idea&…

从零开始学习 Java:简单易懂的入门指南之IO序列化、打印流、压缩流(三十三)

序列化、打印流、压缩流、工具包 1. 序列化1.1 概述1.2 ObjectOutputStream类构造方法序列化操作 1.3 ObjectInputStream类构造方法反序列化操作1反序列化操作2 1.4 练习&#xff1a;序列化集合案例分析案例实现 2. 打印流2.1 概述2.2 PrintStream类构造方法改变打印流向 3. 压…

Docker Mysql实战:docker compose 搭建Mysql

1、docker-compose-mysql文件准备 进入/home/docker目录&#xff0c;新建docker-compose-mysql.yml文件&#xff0c;内容如下&#xff1a; version: 3.0 services:mysql:image: "mysql:5.7"container_name: "mysql"environment:MYSQL_ROOT_PASSWORD: &q…

战神引擎传奇假设教程

战神引擎传奇假设教程 --------------------------------------------------------------------------------------------------- 传奇这款游戏可以说是一代人的回忆&#xff0c;特别是8090后&#xff0c;传奇对他们有着许许多多的难忘的回忆&#xff0c; 随着时代的发展&…

【内网穿透】Docker部署Drupal并实现公网访问

目录 前言 1. Docker安装Drupal 2. 本地局域网访问 3 . Linux 安装cpolar 4. 配置Drupal公网访问地址 5. 公网远程访问Drupal 6. 固定Drupal 公网地址 前言 Dupal是一个强大的CMS&#xff0c;适用于各种不同的网站项目&#xff0c;从小型个人博客到大型企业级门户网站。…

win32汇编源程序结构

先看一个实例&#xff1a; ; 使用 Win32ASM 写的 Hello, world 程序 ;>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>&g…

three.js学习之vR展厅

目标 1、需要会的知识点three.js的场景&#xff0c;摄像机&#xff0c;渲染器&#xff0c;轨道控制器&#xff0c;坐标轴&#xff0c;场景适配&#xff0c;渲染循环创建立方缓冲几何体、纹理、3d物体 实现&#xff1a;创建立方几何体&#xff0c;纹理贴图镜面反向渲染&#xf…

Springboot使用sqlcipher4加密sqlite数据库

在有些业务场景&#xff0c;需要使用sqlite数据库&#xff0c;但sqlite数据库生的db文件&#xff0c;是明文的&#xff0c;该文件被别人拿到&#xff0c;就可以看到里面的所有数据&#xff0c;非常不安全&#xff0c;市面上有很多对sqlite数据库文件加密的方式&#xff0c;但都…

vscode远程ssh服务器且更改服务器别名

目录 1、打开VS Code并确保已安装"Remote - SSH"扩展。如果尚未安装&#xff0c;请在扩展市场中搜索并安装它。 2、单击左下角的"Remote Explorer"图标&#xff0c;打开远程资源管理器。 3、在远程资源管理器中&#xff0c;单击右上角的齿轮图标&#x…

1712A 300A嵌入式电源系统

1712A 300A嵌入式电源系统 1712A 300A嵌入式电源系统采用模块化设计、组合式结构&#xff0c;由控制器、整流模块、交流配电单元、直流配电单元等组成。该系统将交流电转换成稳定的-48V直流电&#xff0c;用于铁塔、移动、电信、联通等公司的传输、接入网&#xff0c;以及专网等…

vscode 连接ubuntu git下载缓慢

在ubuntu20.04下载&#xff1a; git clone https://github.com/introlab/rtabmap.git src/rtabmap 挂掉情况 export https_proxyhttp://10.10.10.176:7890export http_proxyhttp://10.10.10.176:7890 其中 10.10.10.176是我本机的ip地址&#xff0c;7890是我的代理后几位 如…

【PPT】ppt里面使用svg图标

要想编辑好的PPT&#xff0c;少不了小图标的美化&#xff0c;图标可以使PPT变得更有趣&#xff0c;更易懂&#xff0c;更美观。 对于png&#xff0c;主要处理它的颜色&#xff0c;可使用【重新着色】功能。 对于jpg&#xff0c;主要处理它的背景&#xff0c;删除背景后同png处…