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 <= 16
  • s 仅由小写英文字母组成

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 <= 20
  • s 仅由数字组成

思路几乎一致,都是要求分割的字符串所有情况,唯一不同的是这道题有些额外的条件,但都很好解决,具体代码如下:

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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/10276.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

服务器虚拟化技术详解与实战:架构、部署与优化

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 引言 在现代 IT 基础架构中&#xff0c;服务器虚拟化已成为提高资源利用率、降低运维成本、提升系统灵活性的重要手段。通过服务…

记录一次,PyQT的报错,多线程Udp失效,使用工具如netstat来检查端口使用情况。

1.问题 报错Exception in thread Thread-1: Traceback (most recent call last): File "threading.py", line 932, in _bootstrap_inner File "threading.py", line 870, in run File "main.py", line 456, in udp_recv IndexError: list…

【PyTorch】6.张量运算函数:一键开启!PyTorch 张量函数的宝藏工厂

目录 1. 常见运算函数 个人主页&#xff1a;Icomi 专栏地址&#xff1a;PyTorch入门 在深度学习蓬勃发展的当下&#xff0c;PyTorch 是不可或缺的工具。它作为强大的深度学习框架&#xff0c;为构建和训练神经网络提供了高效且灵活的平台。神经网络作为人工智能的核心技术&…

线段树 算法

文章目录 基础知识适用场景小结 题目概述题目详解300.最长递增子序列2407.最长递增子序列 II 基础知识 线段树和树状数组都只是一个工具来的&#xff0c;题目并不会一下子就告诉你这个题目用到线段树和树状数组&#xff0c;这个取决于你想使用的数据结构以及所要优化的方向 线…

JVM_类的加载、链接、初始化、卸载、主动使用、被动使用

①. 说说类加载分几步&#xff1f; ①. 按照Java虚拟机规范,从class文件到加载到内存中的类,到类卸载出内存为止,它的整个生命周期包括如下7个阶段: 第一过程的加载(loading)也称为装载验证、准备、解析3个部分统称为链接(Linking)在Java中数据类型分为基本数据类型和引用数据…

SpringBoot+Vue的理解(含axios/ajax)-前后端交互前端篇

文章目录 引言SpringBootThymeleafVueSpringBootSpringBootVue&#xff08;前端&#xff09;axios/ajaxVue作用响应式动态绑定单页面应用SPA前端路由 前端路由URL和后端API URL的区别前端路由的数据从哪里来的 Vue和只用三件套axios区别 关于地址栏url和axios请求不一致VueJSPS…

socket实现HTTP请求,参考HttpURLConnection源码解析

背景 有台服务器&#xff0c;网卡绑定有2个ip地址&#xff0c;分别为&#xff1a; A&#xff1a;192.168.111.201 B&#xff1a;192.168.111.202 在这台服务器请求目标地址 C&#xff1a;192.168.111.203 时必须使用B作为源地址才能访问目标地址C&#xff0c;在这台服务器默认…

Hive:复杂数据类型之Map函数

Map函数 是Hive里面的一种复杂数据类型, 用于存储键值对集合。Map中的键和值可以是基础类型或复合类型&#xff0c;这使得Map在处理需要关联存储信息的数据时非常有用。 定义map时,需声明2个属性: key 和 value , map中是 key value 组成一个元素 key-value, key必须为原始类…

项目集成GateWay

文章目录 1.环境搭建1.创建sunrays-common-cloud-gateway-starter模块2.目录结构3.自动配置1.GateWayAutoConfiguration.java2.spring.factories 3.pom.xml4.注意&#xff1a;GateWay不能跟Web一起引入&#xff01; 1.环境搭建 1.创建sunrays-common-cloud-gateway-starter模块…

【C++高并发服务器WebServer】-9:多线程开发

本文目录 一、线程概述1.1 线程和进程的区别1.2 线程之间共享和非共享资源1.3 NPTL 二、线程操作2.1 pthread_create2.2 pthread_exit2.3 pthread_join2.4 pthread_detach2.5 patch_cancel2.6 pthread_attr 三、实战demo四、线程同步五、死锁六、读写锁七、生产消费者模型 一、…

python学opencv|读取图像(四十七)使用cv2.bitwise_not()函数实现图像按位取反运算

【0】基础定义 按位与运算&#xff1a;两个等长度二进制数上下对齐&#xff0c;全1取1&#xff0c;其余取0。按位或运算&#xff1a;两个等长度二进制数上下对齐&#xff0c;有1取1&#xff0c;其余取0。 按位取反运算&#xff1a;一个二进制数&#xff0c;0变1,1变0。 【1】…

初二回娘家

昨天下午在相亲相爱一家人群里聊天&#xff0c;今天来娘家拜年。 聊天结束后&#xff0c;开始准备今天的菜肴&#xff0c;梳理了一下&#xff0c;凉菜&#xff0c;热菜&#xff0c;碗菜。 上次做菜&#xff0c;粉丝感觉泡的不透&#xff0c;有的硬&#xff0c;这次使用开水浸泡…

“星门计划对AI未来的意义——以及谁将掌控它”

“星门计划对AI未来的意义——以及谁将掌控它” 图片由DALL-E 3生成 就在几天前&#xff0c;唐纳德特朗普宣布了“星门计划”&#xff0c;OpenAI随即跟进&#xff0c;分享了更多细节。他们明确表示&#xff0c;计划在未来四年内投资5000亿美元&#xff0c;在美国为OpenAI构建一…

内外网文件摆渡企业常见应用场景和对应方案

在如今的企业环境中&#xff0c;内外网文件摆渡的需求越来越常见&#xff0c;也变得越来越重要。随着信息化的不断推进&#xff0c;企业内部和外部之间的数据交换越来越频繁&#xff0c;如何安全、高效地进行文件传输成了一个关键问题。今天&#xff0c;咱就来聊聊内外网文件摆…

2025一区新风口:小波变换+KAN!速占!

今天给大家分享一个能让审稿人眼前一亮&#xff0c;好发一区的idea&#xff1a;小波变换KAN&#xff01; 一方面&#xff1a;KAN刚中稿ICLR25&#xff0c;正是风口上&#xff0c;与小波变换的结合还处于起步阶段&#xff0c;正是红利期&#xff0c;创新空间广阔。 另一方面&a…

idea修改模块名导致程序编译出错

本文简单描述分别用Idea菜单、pom.xml文件管理项目模块module 踩过的坑&#xff1a; 通过idea菜单创建模块&#xff0c;并用idea菜单修改模块名&#xff0c;结构程序编译报错&#xff0c;出错的代码莫名奇妙。双击maven弹窗clean时&#xff0c;还是报错。因为模块是新建的&am…

线程池以及在QT中的接口使用

文章目录 前言线程池架构组成**一、任务队列&#xff08;Task Queue&#xff09;****二、工作线程组&#xff08;Worker Threads&#xff09;****三、管理者线程&#xff08;Manager Thread&#xff09;** 系统协作流程图解 一、QRunnable二、QThreadPool三、线程池的应用场景W…

P1044 [NOIP2003 普及组] 栈 C语言

P1044 [NOIP2003 普及组] 栈 - 洛谷 | 计算机科学教育新生态 题目背景 栈是计算机中经典的数据结构&#xff0c;简单的说&#xff0c;栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作&#xff0c;即 pop&#xff08;从栈顶弹出一个元素&#xff09;和 pus…

随机矩阵投影长度保持引理及其证明

原论文中的引理 2 \textbf{2} 2 引理 2 \textbf{2} 2的内容​​ &#x1f449;前提 1 1 1&#xff1a;设一个随机矩阵 S ( s i j ) ∈ R t d S\text{}(s_{ij})\text{∈}\mathbb{R}^{t\text{}d} S(sij​)∈Rtd&#xff0c;每个元素 s i j s_{ij} sij​独立同分布于 N ( 0 , …

CF 761A.Dasha and Stairs(Java实现)

题目分析 大概意思是输入偶数值奇数值&#xff0c;判断是否能够凑成一连串数字 思路分析 能够连成一串数字的条件考虑&#xff1a;1.偶数与奇数差为1&#xff1b;2.偶数与奇数相等&#xff0c;且不为0 代码 import java.util.*;public class Main {public static void…