力扣hot100 分割回文串 集合 dfs
Problem: 131. 分割回文串
文章目录
- 思路
- Code
- 💖 DP预处理版
思路
👨🏫 参考题解
Code

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {int n;//字符长度List<List<String>> res = new ArrayList<>();char[] ss;//字符数组public List<List<String>> partition(String s) {n = s.length();if (n == 0)return res;ss = s.toCharArray();dfs(0, new Stack<String>());return res;}
// idx 是当前未分割段的起点包含)
// path 是当前已分割的字符串集合private void dfs(int idx, Stack<String> path) {if (idx == n) //n以前的字符都分割了,结算{res.add(new ArrayList<String>(path));return;}for (int i = idx; i < n; i++) // i 枚举的是截取的位置{if (!check(idx, i))//不回文直接跳过continue;path.add(new String(ss, idx, i + 1 - idx));dfs(i + 1, path);// i 是截取的位置,i+1 是未截取段的起点path.pop();}}// 判断 ss[] 中 [l,r] 区间是否为回文子串,回文返回 trueprivate boolean check(int l, int r) {while (l < r)if (ss[l++] != ss[r--])return false;return true;}
}
💖 DP预处理版

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<String>> partition(String s) {int len = s.length();List<List<String>> res = new ArrayList<>();if (len == 0) {return res;}char[] charArray = s.toCharArray();// 预处理// 状态:dp[i][j] 表示 s[i][j] 是否是回文boolean[][] dp = new boolean[len][len];// 状态转移方程:在 s[i] == s[j] 的时候,dp[i][j] 参考 dp[i + 1][j - 1]for (int right = 0; right < len; right++) {// 注意:left <= right 取等号表示 1 个字符的时候也需要判断for (int left = 0; left <= right; left++) {if (charArray[left] == charArray[right] && (right - left <= 2 || dp[left + 1][right - 1])) {dp[left][right] = true;}}}Deque<String> stack = new ArrayDeque<>();dfs(s, 0, len, dp, stack, res);return res;}private void dfs(String s, int index, int len, boolean[][] dp, Deque<String> path, List<List<String>> res) {if (index == len) {res.add(new ArrayList<>(path));return;}for (int i = index; i < len; i++) {if (dp[index][i]) {path.addLast(s.substring(index, i + 1));dfs(s, i + 1, len, dp, path, res);path.removeLast();}}}
}
相关文章:
力扣hot100 分割回文串 集合 dfs
Problem: 131. 分割回文串 文章目录 思路Code💖 DP预处理版 思路 👨🏫 参考题解 Code import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Deque; import java.util.List;public class Solution {int n;//字符…...
C# 一个快速读取写入操作execl的方法封装
这里封装了3个实用类ExcelDataReaderExtensions,ExcelDataSetConfiguration,ExcelDataTableConfiguration和一个实用代码参考: using ExcelDataReader; using System; using System.Collections.Generic; using System.Linq; using System.T…...
axios结合ts使用,取消请求,全局统一获取数据,抛出错误信息
通常在开发时,后端向前端返回的数据可以如下: 1 使用restful api充分利用http状态码,然后在data中追加code字段,请求成功返回200,请求失败返回404,401,500等状态码,并且在code字段中给出详细的字符串信息2 再包一层&a…...
MongoDB:从容器使用到 Mongosh、Python/Node.js 数据操作(结构清晰万字长文)
文章目录 1. 容器与应用之间的关系介绍2. 使用 Docker 容器安装 MongoDB3. Mongosh 操作3.1 Mongosh 连接到 MongoDB3.2 基础操作与 CRUD 4. Python 操作 MongoDB5. Nodejs 操作 MongoDB5.1 Mongodb 和 Mongoose5.2 推荐在项目中使用 Mongoose 参考文献 1. 容器与应用之间的关系…...
超越传统—Clean架构打造现代Android架构指南
超越传统—Clean架构打造现代Android架构指南 1. 引言 在过去几年里,Android应用开发经历了巨大的变革和发展。随着移动设备的普及和用户对应用的期望不断提高,开发人员面临着更多的挑战和需求。传统的Android架构在应对这些挑战和需求时显得有些力不从…...
WebGL开发项目的类型
WebGL(Web Graphics Library)是一种用于在Web浏览器中渲染交互式3D和2D图形的JavaScript API。使用WebGL,可以开发各种类型的项目,包括但不限于以下几种,希望对大家有所帮助。北京木奇移动技术有限公司,专业…...
CUDA编程- - GPU线程的理解 thread,block,grid - 学习记录
GPU线程的理解 thread,block,grid 一、从 cpu 多线程角度理解 gpu 多线程1、cpu 多线程并行加速2、gpu多线程并行加速2.1、cpu 线程与 gpu 线程的理解(核函数)2.1.1 、第一步:编写核函数2.1.2、第二步:调用核函数(使用…...
yum 报错 ZLIB_1.2.3.3 not defined in file libz.so.1
这篇记录工作中发现的,库文件被修改导致 yum 无法正常使用的问题排查过程 问题描述 1)执行yum 报错说python2.7.5 结构异常,发现/usr/bin/yum 的解释器被修改过,恢复成/usr/bin/python即可 2)恢复后,发现…...
数字孪生智慧能源电力Web3D可视化云平台合集
前言 能源电力的经济发展是中国式现代化的强大动力,是经济社会发展的必要生产要素,电力成本变化直接关系到工业生产、交通运输、农业生产、居民生活等各个方面,合理、经济的能源成本能够促进社会用能服务水平提升、支撑区域产业发展…...
DataTable.Load(reader)注意事项
对于在C#中操作数据库查询,这样的代码很常见: using var cmd ExecuteCommand(sql); using var reader cmd.ExecuteReader(); DataTable dt new DataTable(); dt.Load(reader); ...一般的查询是没问题的,但是如果涉及主键列的查询…...
DC-DNS(域名解析服务)(23国赛真题)
2023全国职业院校技能大赛网络系统管理赛项–模块B:服务部署(WindowServer2022) 文章目录 题目配置步骤安装及配置DNS服务。创建正向区域,添加必要的域名解析记录。配置TXT记录,配置域名反向PTR。无法解析的域名统一交由IspSrv进行解析验证配置chinaskills.com正向区域配置…...
日志之Loki详细讲解
文章目录 1 Loki1.1 引言1.2 Loki工作方式1.2.1 日志解析格式1.2.2 日志搜集架构模式1.2.3 Loki部署模式 1.3 服务端部署1.3.1 AllInOne部署模式1.3.1.1 k8s部署1.3.1.2 创建configmap1.3.1.3 创建持久化存储1.3.1.4 创建应用1.3.1.5 验证部署结果 1.3.2 裸机部署 1.4 Promtail…...
Mongodb投射中的$slice,正向反向跳过要搞清楚
在投射中,使用$操作符和$elemMatch返回数组中第一个符合查询条件的元素。而在投射中使用$slice, 能够返回指定数量的数组元素。 定义 投射中使用$slice命令,指定查询结果中返回数组元素的数量。 语法 db.collection.find(<query>,{<arrayFi…...
类和对象 第六部分 继承 第一部分:继承的语法
一.继承的概念 继承是面向对象的三大特性之一 有些类与类之间存在特殊的关系,例如下图: 我们可以发现,下级别的成员除了拥有上一级的共性,还有自己的特性,这个时候,我们可以讨论利用继承的技术,…...
githacker安装详细教程,linux添加环境变量详细教程(见标题三)
笔者是ctf小白,这两天也是遇到.git泄露的题目,需要工具来解决问题,在下载和使用的过程中也是遇到很多问题,写此篇记录经验,以供学习 在本篇标题三中有详细介绍了Linux系统添加环境变量的操作教程,以供学习 …...
2401Idea用GradleKotlin编译Java控制台中文出乱码解决
解决方法 解决方法1 在项目 build.gradle.kts 文件中加入 tasks.withType<JavaCompile> {options.encoding "UTF-8" } tasks.withType<JavaExec> {systemProperty("file.encoding", "utf-8") }经测试, 只加 tasks.withType<…...
Day39 62不同路径 63不同路径II 343整数拆分 96不同的二叉搜索树
62 不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径&#…...
JavaScript 的 ~~ 运算和floor 的性能差异
在JavaScript中,~~(双波浪号)和Math.floor()都可以用于向下取整,但它们在行为和性能上有一些差异。要测试这两者之间的性能差异,你可以使用JavaScript的performance.now()方法来进行基准测试。 行为差异 Math.floor()…...
AtCoder Beginner Contest 338F - Negative Traveling Salesman【floyd+状态压缩dp】
原题链接:https://atcoder.jp/contests/abc338/tasks/abc338_f Time Limit: 6 sec / Memory Limit: 1024 MB Score: 500 points、 问题陈述 有一个有N个顶点和M条边的加权简单有向图。顶点的编号为 1 到 N,i/th 边的权重为 Wi,从顶点 U…...
UDP/TCP协议特点
1.前置知识 定义应用层协议 1.确定客户端和服务端要传递哪些信息 2.约定传输格式 网络上传输的一般是二进制数据/字符串 结构化数据转二进制/字符串 称为序列化 反之称之为反序列化 下面就是传输层了 在TCP/IP协议中,我们以 目的端口,目的IP 源端口 源IP 协议号这样一个五…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...

