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

力扣hot100 分割回文串 集合 dfs

Problem: 131. 分割回文串
1

文章目录

  • 思路
  • 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&#x1f496; DP预处理版 思路 &#x1f468;‍&#x1f3eb; 参考题解 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&#xff0c;ExcelDataSetConfiguration&#xff0c;ExcelDataTableConfiguration和一个实用代码参考&#xff1a; using ExcelDataReader; using System; using System.Collections.Generic; using System.Linq; using System.T…...

axios结合ts使用,取消请求,全局统一获取数据,抛出错误信息

通常在开发时&#xff0c;后端向前端返回的数据可以如下&#xff1a; 1 使用restful api充分利用http状态码&#xff0c;然后在data中追加code字段&#xff0c;请求成功返回200,请求失败返回404,401,500等状态码&#xff0c;并且在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. 引言 在过去几年里&#xff0c;Android应用开发经历了巨大的变革和发展。随着移动设备的普及和用户对应用的期望不断提高&#xff0c;开发人员面临着更多的挑战和需求。传统的Android架构在应对这些挑战和需求时显得有些力不从…...

WebGL开发项目的类型

WebGL&#xff08;Web Graphics Library&#xff09;是一种用于在Web浏览器中渲染交互式3D和2D图形的JavaScript API。使用WebGL&#xff0c;可以开发各种类型的项目&#xff0c;包括但不限于以下几种&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业…...

CUDA编程- - GPU线程的理解 thread,block,grid - 学习记录

GPU线程的理解 thread,block,grid 一、从 cpu 多线程角度理解 gpu 多线程1、cpu 多线程并行加速2、gpu多线程并行加速2.1、cpu 线程与 gpu 线程的理解&#xff08;核函数&#xff09;2.1.1 、第一步&#xff1a;编写核函数2.1.2、第二步&#xff1a;调用核函数&#xff08;使用…...

yum 报错 ZLIB_1.2.3.3 not defined in file libz.so.1

这篇记录工作中发现的&#xff0c;库文件被修改导致 yum 无法正常使用的问题排查过程 问题描述 1&#xff09;执行yum 报错说python2.7.5 结构异常&#xff0c;发现/usr/bin/yum 的解释器被修改过&#xff0c;恢复成/usr/bin/python即可 2&#xff09;恢复后&#xff0c;发现…...

数字孪生智慧能源电力Web3D可视化云平台合集

前言 能源电力的经济发展是中国式现代化的强大动力&#xff0c;是经济社会发展的必要生产要素&#xff0c;电力成本变化直接关系到工业生产、交通运输、农业生产、居民生活等各个方面&#xff0c;合理、经济的能源成本能够促进社会用能服务水平提升、支撑区域产业发展&#xf…...

DataTable.Load(reader)注意事项

对于在C#中操作数据库查询&#xff0c;这样的代码很常见&#xff1a; using var cmd ExecuteCommand(sql); using var reader cmd.ExecuteReader(); DataTable dt new DataTable(); dt.Load(reader); ...一般的查询是没问题的&#xff0c;但是如果涉及主键列的查询&#xf…...

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,正向反向跳过要搞清楚

在投射中&#xff0c;使用$操作符和$elemMatch返回数组中第一个符合查询条件的元素。而在投射中使用$slice, 能够返回指定数量的数组元素。 定义 投射中使用$slice命令&#xff0c;指定查询结果中返回数组元素的数量。 语法 db.collection.find(<query>,{<arrayFi…...

类和对象 第六部分 继承 第一部分:继承的语法

一.继承的概念 继承是面向对象的三大特性之一 有些类与类之间存在特殊的关系&#xff0c;例如下图&#xff1a; 我们可以发现&#xff0c;下级别的成员除了拥有上一级的共性&#xff0c;还有自己的特性&#xff0c;这个时候&#xff0c;我们可以讨论利用继承的技术&#xff0c;…...

githacker安装详细教程,linux添加环境变量详细教程(见标题三)

笔者是ctf小白&#xff0c;这两天也是遇到.git泄露的题目&#xff0c;需要工具来解决问题&#xff0c;在下载和使用的过程中也是遇到很多问题&#xff0c;写此篇记录经验&#xff0c;以供学习 在本篇标题三中有详细介绍了Linux系统添加环境变量的操作教程&#xff0c;以供学习 …...

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 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xff09;。 问总共有多少条不同的路径&#…...

JavaScript 的 ~~ 运算和floor 的性能差异

在JavaScript中&#xff0c;~~&#xff08;双波浪号&#xff09;和Math.floor()都可以用于向下取整&#xff0c;但它们在行为和性能上有一些差异。要测试这两者之间的性能差异&#xff0c;你可以使用JavaScript的performance.now()方法来进行基准测试。 行为差异 Math.floor()…...

AtCoder Beginner Contest 338F - Negative Traveling Salesman【floyd+状态压缩dp】

原题链接&#xff1a;https://atcoder.jp/contests/abc338/tasks/abc338_f Time Limit: 6 sec / Memory Limit: 1024 MB Score: 500 points、 问题陈述 有一个有N个顶点和M条边的加权简单有向图。顶点的编号为 1 到 N&#xff0c;i/th 边的权重为 Wi​&#xff0c;从顶点 U…...

UDP/TCP协议特点

1.前置知识 定义应用层协议 1.确定客户端和服务端要传递哪些信息 2.约定传输格式 网络上传输的一般是二进制数据/字符串 结构化数据转二进制/字符串 称为序列化 反之称之为反序列化 下面就是传输层了 在TCP/IP协议中,我们以 目的端口,目的IP 源端口 源IP 协议号这样一个五…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

结构化文件管理实战:实现目录自动创建与归类

手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题&#xff0c;进而引发后续程序异常。使用工具进行标准化操作&#xff0c;能有效降低出错概率。 需要快速整理大量文件的技术用户而言&#xff0c;这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB&#xff0c;…...