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

LeetCode131. 分割回文串(2024冬季每日一题 4)

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1:

输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2:

输入:s = “a”
输出:[[“a”]]

提示:

1 <= s.length <= 16
s 仅由小写英文字母组成


思路: dfs + 记忆化搜索

  • dfs 递归当前 start 下标开始的字串能如何划分,枚举其右边界
  • 如果当前字串是回文串,则将当前字串加入当前dfs路径,dfs 继续递归剩余的字串
  • 当前路径递归完,遍历下个边界时,需要回溯,删除路径列表中之前的字串
  • 如果递归到 start==n,即已经划分完所有的字串,则将当前路径加入结果集
  • 判断回文串,可以通过记忆化搜索,f[i][j] 用于记录当前状态是否判断过
    • 其中 1 代表是回文串,-1 代表不是,0 代表还没有搜索过
class Solution {
public:vector<vector<string>> res;vector<string> ans;// 1 代表是回文串,-1 代表不是,0 代表还没有搜索过int f[20][20];int n;vector<vector<string>> partition(string s) {n = s.size();dfs(s, 0);return res;}void dfs(string &s, int start){if(start == n){res.push_back(ans);return;}for(int i = start; i < n; i++){if(is_fn(s, start, i) == 1){ans.push_back(s.substr(start, i - start + 1));dfs(s, i + 1);ans.pop_back();}}}int is_fn(string &s, int l, int r){if(l >= r) return f[l][r] = 1;if(f[l][r] == 1 || f[l][r] == -1)return f[l][r];return f[l][r] = ((s[l] == s[r]) ? is_fn(s, l + 1, r - 1): -1);}
};

相关文章:

LeetCode131. 分割回文串(2024冬季每日一题 4)

给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1&#xff1a; 输入&#xff1a;s “aab” 输出&#xff1a;[[“a”,“a”,“b”],[“aa”,“b”]] 示例 2&#xff1a; 输入&#xff1a;s “a…...

万字长文解读深度学习——训练(DeepSpeed、Accelerate)、优化(蒸馏、剪枝、量化)、部署细节

&#x1f33a;历史文章列表&#x1f33a; 深度学习——优化算法、激活函数、归一化、正则化深度学习——权重初始化、评估指标、梯度消失和梯度爆炸深度学习——前向传播与反向传播、神经网络&#xff08;前馈神经网络与反馈神经网络&#xff09;、常见算法概要汇总万字长文解读…...

STM32—独立看门狗(IWDG)和窗口看门狗(WWDG)

概述&#xff1a; WDG(Watchdog) 看门狗&#xff0c;看门狗可以监控程序的运行状态&#xff0c;当程序因为设计漏洞、硬件故障、电磁干扰等原因&#xff0c;出现卡死或跑飞现象时&#xff0c;看门狗能计时复位程序&#xff0c;避免程序陷入长时间的罢工状态&#xff0c;保证系…...

ks8 本地化部署 F5-TTS

huggingface上有一个demo可以打开就能玩 https://huggingface.co/spaces/mrfakename/E2-F5-TTS 上传了一段懂王的演讲片段&#xff0c;然后在 generate text框内填了点古诗词&#xff0c;生成后这语气这效果&#xff0c;离真懂王就差一个手风琴了。 F5-TTS 项目地址&#xf…...

Web组态大屏可视化编辑器

1、零代码、一键构建、一键下载 用户只需通过拖拉拽操作&#xff0c;即可在画布上添加、调整和排列各种设备组件、图表和控件。零代码拖拽方式让用户能够实时预览界面效果&#xff0c;直观地观察布局、样式和数据的变化。 2、实时展示&#xff0c;自动化连接数据&#xff0c;用…...

【comfyui教程】让模特换衣服,comfyui一键搞定!

前言 一键穿上别人的衣服&#xff1f;揭秘ComfyUI模特换装工作流&#xff01; 你有没有想过&#xff0c;某天早晨你起床后&#xff0c;只需轻轻一点&#xff0c;就能穿上明星昨晚在红毯上的华丽礼服&#xff1f;这种听起来像是科幻电影的情节&#xff0c;如今通过ComfyUI模特…...

数据湖与数据仓库的区别

数据湖与数据仓库是两种不同的数据存储和管理方式&#xff0c;它们在多个方面存在显著的区别。以下是对数据湖与数据仓库区别的详细阐述&#xff1a; 一、数据存储方式 数据仓库 通常采用预定义的模式和结构来存储数据。数据在存储前通常经过清洗、转换和整合等处理&#xff0…...

golang分布式缓存项目 Day6 防止缓存击穿

该项目原作者&#xff1a;https://github.com/geektutu/7days-golang。本文旨在记录本人做该项目时的一些疑惑解答以及部分的测试样例以便于本人复习。 1 缓存雪崩、缓存击穿与缓存穿透 概念解析&#xff1a; 缓存雪崩&#xff1a;缓存在同一时刻全部失效&#xff0c;造成瞬…...

Redis高可用-主从复制

这里写目录标题 Redis主从复制主从复制过程环境搭建从节点配置常见问题主从模式缺点 Redis主从复制 虽然 Redis 可以实现单机的数据持久化&#xff0c;但无论是 RDB 也好或者 AOF 也好&#xff0c;都解决不了单点宕机问题&#xff0c;即一旦 redis 服务器本身出现系统故障、硬…...

Angular框架:构建现代Web应用的全面指南

文章目录 前言一、Angular简介二、Angular的核心特性三、Angular的应用场景四、Angular的发展趋势五、如何开始使用Angular结语 前言 在当今高度竞争的互联网环境中&#xff0c;构建高效、响应迅速且易于维护的Web应用成为企业成功的关键。Angular框架以其强大的功能、灵活的架…...

Golang | Leetcode Golang题解之第563题二叉树的坡度

题目&#xff1a; 题解&#xff1a; func findTilt(root *TreeNode) (ans int) {var dfs func(*TreeNode) intdfs func(node *TreeNode) int {if node nil {return 0}sumLeft : dfs(node.Left)sumRight : dfs(node.Right)ans abs(sumLeft - sumRight)return sumLeft sumRi…...

gdb编译教程(支持linux下X86和ARM架构)

1、下载源码 http://ftp.gnu.org/gnu/gdb/ 我下载的8.2版本。 2、下载完后拷贝到linux的x86系统。 3、解压&#xff0c;然后进入到目录下&#xff0c;打开当前目录的命令行窗口。 4、创建一个生成目录。 5、我们先开始x86版本&#xff0c;这个比较简单&#xff0c;不需要配置…...

Android 开发指南:初学者入门

Android 是全球最受欢迎的移动操作系统之一&#xff0c;为开发者提供了丰富的工具和资源来创建各种类型的应用程序。本文将为你提供一个全面的入门指南&#xff0c;帮助你从零开始学习 Android 开发。 目录 1. 了解 Android 平台[1]2. 设置开发环境[2]3. 学习基础知识[3]4. 创…...

镭速大文件传输软件向金融银行的文档管理提供高效的解决方案

随着数字化浪潮的推进&#xff0c;金融机构对文档处理和大文件传输的需求日益增长。无论是中央机构还是地方分行&#xff0c;他们都急需一套强大的文档管理系统来应对日益庞大的数据量和日益复杂的业务需求。如何有效地管理海量文档&#xff0c;成为了金融机构面临的一大挑战。…...

D64【python 接口自动化学习】- python基础之数据库

day64 SQL-DQL-基础查询 学习日期&#xff1a;20241110 学习目标&#xff1a;MySQL数据库-- 133 SQL-DQL-基础查询 学习笔记&#xff1a; 基础数据查询 基础数据查询-过滤 总结 基础查询的语法&#xff1a;select 字段列表|* from 表过滤查询的语法&#xff1a;select 字段…...

HTTP 客户端怎么向 Spring Cloud Sleuth 传输跟踪 ID

在 Spring Cloud Sleuth 的请求链路追踪中&#xff0c;X-B3-TraceId 是第二个 ID&#xff0c;X-B3-SpanId 是第三个 ID。以下是 Sleuth 中各个追踪标识的含义&#xff1a; X-B3-TraceId&#xff1a;表示整个请求链路的全局唯一 ID&#xff0c;用于跟踪请求在多个服务间的流转。…...

为什么hbase在大数据领域渐渐消失

HBase 曾是大数据存储领域的标杆之一,凭借其强大的分布式、列式存储和高扩展性,广泛应用于电商、社交网络、金融等需要海量数据管理的场景。然而,近年来 HBase 的使用确实在减少,这主要是因为数据技术栈的演变和用户需求的变化。以下是一些主要原因: 1. 复杂的运维和管理…...

【GPTs】EmojiAI:轻松生成趣味表情翻译

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | GPTs应用实例 文章目录 &#x1f4af;GPTs指令&#x1f4af;前言&#x1f4af;EmojiAI主要功能适用场景优点缺点 &#x1f4af;小结 &#x1f4af;GPTs指令 中文翻译&#xff1a; 此 GPT 的主要角色是为英文文本提供幽默…...

中国车牌分类

从颜色和单双层分类(不考虑临时车牌) 黄单黄双黄绿单蓝单蓝双绿单绿双黑单黑双白单白双 #特殊文字 挂使港澳学警领临...

边缘计算在工业互联网中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 边缘计算在工业互联网中的应用 边缘计算在工业互联网中的应用 边缘计算在工业互联网中的应用 引言 边缘计算概述 定义与原理 发展…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

【51单片机】4. 模块化编程与LCD1602Debug

1. 什么是模块化编程 传统编程会将所有函数放在main.c中&#xff0c;如果使用的模块多&#xff0c;一个文件内会有很多代码&#xff0c;不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里&#xff0c;在.h文件里提供外部可调用函数声明&#xff0c;其他.c文…...

大模型真的像人一样“思考”和“理解”吗?​

Yann LeCun 新研究的核心探讨&#xff1a;大语言模型&#xff08;LLM&#xff09;的“理解”和“思考”方式与人类认知的根本差异。 核心问题&#xff1a;大模型真的像人一样“思考”和“理解”吗&#xff1f; 人类的思考方式&#xff1a; 你的大脑是个超级整理师。面对海量信…...