当前位置: 首页 > 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;《热点资讯》 边缘计算在工业互联网中的应用 边缘计算在工业互联网中的应用 边缘计算在工业互联网中的应用 引言 边缘计算概述 定义与原理 发展…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...