Leetcode 131 分割回文串(纯DFS)
131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/
https://leetcode.cn/problems/palindrome-partitioning/
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
DFS方案1：初始化一个代表分割点的01数组，然后对这个数组的状态使用dfs搜索。这个方案耗时长，空间复杂度也不小。具体代码如下：
class Solution {
public:vector<vector<string>> ans;bool cutoff[20] = {false};//代表分割点的01数组bool check(string s)//判断回文串{string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(string s,int cur)//枚举每一个位置，有在该点分割与不分割两种情况{if(cur == s.size()){vector<string> temp;int i = 0;while(true){string t;t.push_back(s[i]);i++;while(!cutoff[i]){t.push_back(s[i]);i++;}if(!check(t))return;else temp.push_back(t);if (i >= s.size())break;}ans.push_back(temp);return;}cutoff[cur] = true;dfs(s,cur+1);cutoff[cur] = false;dfs(s,cur+1);}vector<vector<string>> partition(string s) {//为了整体代码和谐，将首尾都设为分割cutoff[0] = true;cutoff[s.size()] = true;dfs(s,1);return ans;}
};DFS方案2：从前到后直接枚举分割点。如下图：
这个方案更快些，具体差别在该方案能及时排除不可能选项，而不是等上一个方案把所有可能情况全列出来然后对每个依次排除。代码具体如下：
class Solution {
public:vector<vector<string>> ans;vector<string> temp;bool check(string s){string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始点{if(startindex==s.size()){ans.push_back(temp);return;}for(int i = startindex;i<s.size();++i){string str = s.substr(startindex,i-startindex + 1);if(check(str)){temp.push_back(str);dfs(i+1,s);temp.pop_back();}else continue;}}vector<vector<string>> partition(string s) {dfs(0,s);return ans;}
};顺便说一道几乎一样的题：
93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s仅由数字组成
思路几乎一致，都是要求分割的字符串所有情况，唯一不同的是这道题有些额外的条件，但都很好解决，具体代码如下：
class Solution {
public:vector<string> ans;vector<string> temp;inline int transform(string s)//字符串转数字{int t = 0;int re = 0;for(int i = s.size()-1;i>=0;i--,t++){re+=(s[i] - '0')*pow(10,t);}return re;}bool check(string s){string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始点{if(temp.size()>4)//很明显的剪枝return;if(startindex==s.size()&&temp.size()==4){string str;for(int i = 0;i<temp.size();++i){for(int j = 0;j<temp[i].size();++j){str.push_back(temp[i][j]);}str.push_back('.');}str.pop_back();ans.push_back(str);return;}for(int i = startindex;i<s.size();++i){string str = s.substr(startindex,i-startindex + 1);if((str.size()>=2&&str[0] == '0')||str.size()>3||transform(str)>255)//由题得出的筛选条件continue;temp.push_back(str);dfs(i+1,s);temp.pop_back();}}vector<string> restoreIpAddresses(string s) {dfs(0,s);return ans;}
};相关文章：
)
Leetcode 131 分割回文串(纯DFS)
131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/https://leetcode.cn/problems/palindrome-partitioning/ 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1：…...
我的AI工具箱Tauri+Django内容生产介绍和使用
在现代内容生产环境中，高效、自动化的工具能够显著提升生产力，降低人工成本。Tauri 与 Django 结合打造的工作箱，集成了强大的 音频处理、视频剪辑、内容下载 以及 AI 文章撰写 等模块，帮助用户在多媒体内容生产的各个环节实现高效…...
“星门计划对AI未来的意义——以及谁将掌控它”
“星门计划对AI未来的意义——以及谁将掌控它” 图片由DALL-E 3生成 就在几天前，唐纳德特朗普宣布了“星门计划”，OpenAI随即跟进，分享了更多细节。他们明确表示，计划在未来四年内投资5000亿美元，在美国为OpenAI构建一…...
：结构方程模型用于研究数量遗传学中的因果表型网络)
论文阅读(八)：结构方程模型用于研究数量遗传学中的因果表型网络
1.论文链接：Structural Equation Models for Studying Causal Phenotype Networks in Quantitative Genetics 摘要： 表型性状可能在它们之间发挥因果作用。例如，农业物种的高产可能会增加某些疾病的易感性，相反，疾病的…...
【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】1.25 视觉风暴：NumPy驱动数据可视化
1.25 视觉风暴：NumPy驱动数据可视化 目录 #mermaid-svg-i3nKPm64ZuQ9UcNI {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-i3nKPm64ZuQ9UcNI .error-icon{fill:#552222;}#mermaid-svg-i3nKPm64ZuQ9UcNI …...
Linux Samba 低版本漏洞（远程控制）复现与剖析
目录 前言 漏洞介绍 漏洞原理 产生条件 漏洞影响 防御措施 复现过程 结语 前言 在网络安全的复杂生态中，系统漏洞的探索与防范始终是保障数字世界安全稳定运行的关键所在。Linux Samba 作为一款在网络共享服务领域应用极为广泛的软件，其低版本中…...
solidity基础 -- 可视范围
在 Solidity 编程语言中，可视范围（Visibility）用于控制合约中变量和函数的访问权限。这对于确保合约的安全性、模块化以及代码的可维护性至关重要。Solidity 提供了四种可视范围修饰符：public、private、external 和 internal。以…...
Spring Boot - 数据库集成07 - 数据库连接池
数据库连接池 文章目录 数据库连接池一：知识准备1：什么是数据库连接池？2：数据库连接池基本原理 二：HikariCP连接池1：简单使用2：进一步理解2.1：是SpringBoot2.x默认连接池2.2…...
智云-一个抓取web流量的轻量级蜜罐-k8s快速搭建教程
智云-一个抓取web流量的轻量级蜜罐-k8s快速搭建教程 github地址 https://github.com/xiaoxiaoranxxx/POT-ZHIYUN k8s搭建教程 首先下载代码文件 git clone https://github.com/xiaoxiaoranxxx/POT-ZHIYUN.git cd POT-ZHIYUN编译镜像 代码相关文件在github https://github.com/x…...
MySQL 事件调度器
MySQL 事件调度器确实是一个更方便且内置的解决方案，可以在 MySQL 服务器端自动定期执行表优化操作，无需依赖外部工具或应用程序代码。这种方式也能减少数据库维护的复杂性，尤其适用于在数据库频繁更新或删除时进行自动化优化。 使用 MySQL …...
3 Spark SQL
Spark SQL 1. 数据分析方式2. SparkSQL 前世今生3. Hive 和 SparkSQL4. 数据分类和 SparkSQL 适用场景1) 结构化数据2) 半结构化数据3) 总结 5. Spark SQL 数据抽象1) DataFrame2) DataSet3) RDD、DataFrame、DataSet 的区别4) 总结 6. Spark SQL 应用1) 创建 DataFrame/DataSe…...
多头潜在注意力（MLA）：让大模型“轻装上阵”的技术革新——从DeepSeek看下一代语言模型的高效之路
多头潜在注意力（MLA）：让大模型“轻装上阵”的技术革新 ——从DeepSeek看下一代语言模型的高效之路 大模型的“内存焦虑” 当ChatGPT等大语言模型（LLM）惊艳世界时，很少有人意识到它们背后隐藏的“内存焦虑”…...
Spring AI 在微服务中的应用：支持分布式 AI 推理
1. 引言 在现代企业中，微服务架构 已成为开发复杂系统的主流方式，而 AI 模型推理 也越来越多地被集成到业务流程中。如何在分布式微服务架构下高效地集成 Spring AI，使多个服务可以协同完成 AI 任务，并支持分布式 AI 推理&#x…...
赛博算卦之周易六十四卦JAVA实现：六幺算尽天下事，梅花化解天下苦。
佬们过年好呀~新年第一篇博客让我们来场赛博算命吧！ 更多文章：个人主页 系列文章：JAVA专栏 欢迎各位大佬来访哦~互三必回！！！ 文章目录 #一、文化背景概述1.文化起源2.起卦步骤 #二、卦象解读#三、just do i…...
)
数据分析系列--⑤RapidMiner进行关联分析(中文数据案例)
一、数据集 二、数据预处理 1.读取数据、拆分、重命名 2.数据预处理 三、关联分析 四、结论 一、数据集 点击下载数据集shopping_basket.xlsx ,这个数据集专门使用中文数据来进行分析. 二、数据预处理 1.读取数据、拆分、重命名 2.数据预处理 三、关联分析 四、结论 Ok…...
fpga系列 HDL：XILINX Vivado Vitis 高层次综合（HLS） 实现 EBAZ板LED控制（下）
补充代码，将clk之外的输入都设置能使其运行的默认值 timescale 1ns / 1ps module HLSLED(input wire clk ,input wire rst_n ,output wire led);wire led_o_i 0;reg rst 0;wire led_o_o_ap_vld;hlsv1_0 your_instance_name (.led_o_o_ap_vld(led_o_o_ap_vld), /…...
设计模式面试题
一、工厂方法模式: 1.简单工厂模式: (1).抽象产品:定义了产品的规范，描述了产品的主要特性和功能 (2).具体产品:实现或继承抽象产品的子类 (3).具体工厂:提供了创建产品的方法，调用者通过该方法来获取产品 所有产品都共有一个工厂，如果新…...
7层还是4层？网络模型又为什么要分层？
~犬📰余~ “我欲贱而贵，愚而智，贫而富，可乎？ 曰：其唯学乎” 一、为什么要分层 \quad 网络通信的复杂性促使我们需要一种分层的方法来理解和管理网络。就像建筑一样，我们不会把所有功能都混在一起…...
12.udp
12.udp **1. UDP特性****2. UDP编程框架（C/S模式）****3. UDP发送接收函数****4. UDP编程练习** 1. UDP特性 连接特性：无链接，通信前无需像TCP那样建立连接。可靠性：不可靠，不保证数据按序到达、不保证数据…...
【Leetcode 热题 100】32. 最长有效括号
问题背景 给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。 数据约束 0 ≤ s . l e n g t h ≤ 3 1 0 4 0 \le s.length \le 3 \times 10 ^ 4 0≤s.length≤3104 s [ i ] s[i] s[i] 为 ‘(’ 或 ‘…...
Python NumPy（8）：NumPy 位运算、NumPy 字符串函数
1 NumPy 位运算 位运算是一种在二进制数字的位级别上进行操作的一类运算，它们直接操作二进制数字的各个位，而不考虑数字的整体值。NumPy 提供了一系列位运算函数，允许对数组中的元素进行逐位操作，这些操作与 Python 的位运算符类似…...
Fork/Join框架_任务分解与并行执行
1 概述 Fork/Join框架是Java 7引入的一个用于并行执行任务的框架。它特别适用于可以递归分解为多个子任务的工作，每个子任务可以独立执行，并且结果可以合并以获得最终结果。Fork/Join框架通过工作窃取（work-stealing）算法提高了多核处理器上的任务执行效率。 2 核心组件 …...
【大厂AI实践】OPPO：大规模知识图谱及其在小布助手中的应用
导读：OPPO知识图谱是OPPO数智工程系统小布助手团队主导、多团队协作建设的自研大规模通用知识图谱，目前已达到数亿实体和数十亿三元组的规模，主要落地在小布助手知识问答、电商搜索等场景。 本文主要分享OPPO知识图谱建设过程中算法相关的技…...
SOME/IP--协议英文原文讲解2
前言 SOME/IP协议越来越多的用于汽车电子行业中，关于协议详细完全的中文资料却没有，所以我将结合工作经验并对照英文原版协议做一系列的文章。基本分三大块： 1. SOME/IP协议讲解 2. SOME/IP-SD协议讲解 3. python/C举例调试讲解 4.1 Speci…...
为大模型提供webui界面的利器：Open WebUI 完全本地离线部署deepseek r1
为大模型提供webui界面的利器：Open WebUI Open WebUI的官网：🏡 Home | Open WebUI 开源代码：WeTab 新标签页 Open WebUI是一个可扩展、功能丰富、用户友好的自托管AI平台，旨在完全离线运行。它支持各种LLM运行程序&am…...
Cyber Security 101-Build Your Cyber Security Career-Security Principles（安全原则）
了解安全三元组以及常见的安全模型和原则。 任务1：介绍 安全已成为一个流行词;每家公司都想声称其产品或服务是安全的。但事实真的如此吗？ 在我们开始讨论不同的安全原则之前，了解我们正在保护资产的对手至关重要。您是否试图阻止蹒跚学步…...
react-native网络调试工具Reactotron保姆级教程
在React Native开发过程中，调试和性能优化是至关重要的环节。今天，就来给大家分享一个非常强大的工具——Reactotron，它就像是一个贴心的助手，能帮助我们更轻松地追踪问题、优化性能。下面就是一份保姆级教程哦！ 一、…...
Progressive Pretext Task Learning for Human Trajectory Prediction | 文献翻译
祥龙回首留胜景，金蛇起舞贺新程。 概述 行人轨迹预测是一项旨在预测行人未来位置的任务，它通常涵盖了从短期到长期的整个时间范围内的轨迹。然而，现有的研究试图通过单一、统一的训练范式来解决整个轨迹预测问题，往往忽视了行人轨…...
并发编程基础 - 并发编程的概念（C++）
前言 在当今多核处理器普及的时代，并发编程成为开发高性能应用程序的关键技术之一。无论是服务器端应用，桌面软件，还是移动应用，并发编程都扮演着重要角色。本文将详细介绍并发编程的基本概念，结合C语言特性ÿ…...
ARM嵌入式学习--第十天（UART）
--UART介绍 UART(Universal Asynchonous Receiver and Transmitter)通用异步接收器，是一种通用串行数据总线，用于异步通信。该总线双向通信，可以实现全双工传输和接收。在嵌入式设计中，UART用来与PC进行通信，包括与监控…...
OpenEuler学习笔记（十七）：OpenEuler搭建Redis高可用生产环境
在OpenEuler上搭建Redis高可用生产环境，通常可以采用Redis Sentinel或Redis Cluster两种方式，以下分别介绍两种方式的搭建步骤： 基于Redis Sentinel的高可用环境搭建 安装Redis 配置软件源：可以使用OpenEuler的默认软件源&#…...
CTF从入门到精通
文章目录 背景知识CTF赛制 背景知识 CTF赛制 1.web安全:通过浏览器访问题目服务器上的网站，寻找网站漏洞(sql注入，xss（钓鱼链接）,文件上传，包含漏洞，xxe，ssrf，命令执行，…...
java入门笔记基础语法篇（4）
变量 在Java中，每个变量都有一个类型（type）。在声明变量时，变量的类型位于变量 名之前。例如： int days; double salary; long earthPopulation; boolean done; 在Java中，每个声明以分号结束。变量名必须…...
【RocketMQ 存储】- broker 端存储单条消息的逻辑
文章目录 1. 前言2. DefaultMessageStore#asyncPutMessage 添加单条消息2.1 DefaultMessageStore#checkStoreStatus 检查存储服务的状态2.2 DefaultMessageStore#checkMessage 校验消息长度是否合法2.3 CommitLog#asyncPutMessage 核心存储逻辑2.4 MappedFile#appendMessage2.5…...
爬虫基础（四）线程 和 进程 及相关知识点
目录 一、线程和进程 （1）进程 （2）线程 （3）区别 二、串行、并发、并行 （1）串行 （2）并行 （3）并发 三、爬虫中的线程和进程 &am…...
29. C语言 可变参数详解
本章目录: 前言可变参数的基本概念可变参数的工作原理如何使用可变参数 示例：计算多个整数的平均值解析： 更复杂的可变参数示例：打印可变数量的字符串解析： 总结 前言 在C语言中，函数参数的数量通常是固定的ÿ…...
Java CAS操作
通过前面的学习认识到了CPU缓存，Java内存模型，以及线程安全的原子、可见、顺序三大特性。本文则重点认识CAS操作，这是Java并发编程常见的一个操作，AbstractQueuedSynchronizer基于此操作提供了丰富的同步器和各种锁。 CAS&#x…...
KNIME：开源 AI 数据科学
KNIME（Konstanz Information Miner）是一款开源且功能强大的数据科学平台，由德国康斯坦茨大学的软件工程师团队开发，自2004年推出以来，广泛应用于数据分析、数据挖掘、机器学习和可视化等领域。以下是对KNIME的深度介绍…...
超级强大的压缩和解压工具,免费解压
软件介绍 今天要给大家分享一款超厉害的软件 ——ZArchiver，在我心中，它堪称安卓平台目前最为强大的解压软件。 之前，我一直使用 MT 管理器来解压文件。然而，MT 管理器存在一些局限性。比如在处理解压分卷文件时，它有时…...
代码随想录_栈与队列
栈与队列 232.用栈实现队列 232. 用栈实现队列 使用栈实现队列的下列操作： push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。 思路: 定义两个栈: 入队栈, 出队栈, 控制出入…...
基于STM32的智能停车场管理系统设计
目录 引言系统设计 硬件设计软件设计 系统功能模块 车辆识别与进出管理模块车位检测与引导模块计费与支付模块数据存储与查询模块远程监控与异常报警模块 控制算法 车牌识别与车辆进出管理算法车位检测与引导算法计费与支付处理算法数据存储与远程反馈算法 代码实现 车辆检测与…...
告别重启！Vue CLI 动态代理配置实战：实现热更新与灵活配置
在前端开发中，代理配置是解决跨域问题的常见手段。尤其是在使用 Vue CLI 进行开发时，我们经常需要通过 devServer.proxy 来配置代理。然而，传统的代理配置通常是静态的，修改后需要重启开发服务器，这在频繁调整代理配置…...
Cocos Creator 3.8 2D 游戏开发知识点整理
目录 Cocos Creator 3.8 2D 游戏开发知识点整理 1. Cocos Creator 3.8 概述 2. 2D 游戏核心组件 (1) 节点（Node）与组件（Component） (2) 渲染组件 (3) UI 组件 3. 动画系统 (1) 传统帧动画 (2) 动画编辑器 (3) Spine 和 …...
【Numpy核心编程攻略：Python数据处理、分析详解与科学计算】1.28 存储之道：跨平台数据持久化方案
好的，我将按照您的要求生成一篇高质量的Python NumPy文章。以下是第28篇《存储之道：跨平台数据持久化方案》的完整内容，包括目录、正文和参考文献。 1.28 存储之道：跨平台数据持久化方案 目录 #mermaid-svg-n1z37AP8obEgptkD {f…...
chrome源码剖析—UI架构消息机制
Chrome 浏览器的 UI 架构是高度模块化且基于现代图形技术和用户界面设计理念构建的。它的 UI 架构涵盖了窗口、标签页、控件、通知、菜单等组件的管理和交互。Chrome 的 UI 基本上是通过 views 框架和 Aura（Chrome 自己的 UI 层）构建的，后者又…...
面试经典150题——图的广度优先搜索
文章目录 1、蛇梯棋1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、最小基因变化2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、单词接龙3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 1、蛇梯棋 1.1 题目链接 点击跳转到题目位置 1.2 题目描述 给你一…...
Day30-【AI思考】-错题分类进阶体系——12维错误定位模型
文章目录 错题分类进阶体系——12维错误定位模型**一、认知层错误（根源性缺陷）****二、操作层错误（执行过程偏差）****三、心理层错误（元认知障碍）****四、进阶错误（专业级陷阱）** 错…...
利用Edu邮箱解锁Notion Pro，提升学习与工作效率
摘要： 本文将详细介绍如何通过Edu教育邮箱申请教育订阅，从而免费获得Notion Pro版的所有高级功能。此外，我们还将简要提及Edu邮箱的其他福利，如申请Azure 100免费VPS和OpenAI。通过对比Notion免费版和Pro版的差异，你将…...
剑指 Offer II 010. 和为 k 的子数组
comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20010.%20%E5%92%8C%E4%B8%BA%20k%20%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/README.md 剑指 Offer II 010. 和为 k 的子数组 题目描述 给定一个正整数数组和一个…...
【外文原版书阅读】《机器学习前置知识》2.用看电影推荐的例子带你深入了解向量点积在机器学习的作用
目录 3.3 Where Are You Looking, Vector? The Dot Product 个人主页：Icomi 大家好，我是Icomi，本专栏是我阅读外文原版书《Before Machine Learning》对于文章中我认为能够增进线性代数与机器学习之间的理解的内容的一个输出，希望…...