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

LeetCode-131. 分割回文串

目录

    • 题目思路
    • 回溯

题目来源
131. 分割回文串

题目思路

切割问题类似组合问题。
例如对于字符串abcdef:

  • 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
  • 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。

抽象为一棵树形结构
在这里插入图片描述
递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。

回溯

  • 1.递归函数参数

全局变量数组path存放切割后回文的子串,二维数组result存放结果集。 (这两个参数可以放到函数参数里)
本题递归函数参数还需要startIndex,因为切割过的地方,不能重复切割,和组合问题也是保持一致的。

    ArrayList<List<String>> result = new ArrayList<>();ArrayList<String> path = new ArrayList<>();void backTracking(String s,int startIndex)
  • 2.递归函数终止条件
    在这里插入图片描述

从树形结构的图中可以看出:切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件。
那么在代码里什么是切割线呢?
在处理组合问题的时候,递归参数需要传入startIndex,表示下一轮递归遍历的起始位置,这个startIndex就是切割线。
终止条件代码如下:

        if(startIndex >= s.length()){// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了result.add(new ArrayList(path));return;}
  • 3.单层搜索的逻辑

来看看在递归循环中如何截取子串呢?
在for (int i = startIndex; i < s.length(); i++)循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文,如果是回文,就加入在path中,path用来记录切割过的回文子串。

        for(int i = startIndex;i<s.length();i++){//如果是回文子串,则记录if(isPalindrome(s,startIndex,i)){String str = s.substring(startIndex,i+1);path.add(str);}else{continue;}//起始位置后移,保证不重复backTracking(s,i+1);path.remove(path.size()-1);}

注意切割过的位置,不能重复切割,所以,backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

判断回文子串

可以使用双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。

    private boolean isPalindrome(String s,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(s.charAt(i) != s.charAt(j)){return false;}}return true;}

整体代码

class Solution {ArrayList<List<String>> result = new ArrayList<>();ArrayList<String> path = new ArrayList<>();public List<List<String>> partition(String s) {if(s == null || s.length() < 1){return result;}backTracking(s,0);return result;}public void backTracking(String s,int startIndex){// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if(startIndex >= s.length()){result.add(new ArrayList(path));return;}for(int i = startIndex;i<s.length();i++){//如果是回文子串,则记录if(isPalindrome(s,startIndex,i)){String str = s.substring(startIndex,i+1);path.add(str);}else{continue;}//起始位置后移,保证不重复backTracking(s,i+1);path.remove(path.size()-1);}}private boolean isPalindrome(String s,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(s.charAt(i) != s.charAt(j)){return false;}}return true;}
}

在这里插入图片描述

相关文章:

LeetCode-131. 分割回文串

目录题目思路回溯题目来源 131. 分割回文串 题目思路 切割问题类似组合问题。 例如对于字符串abcdef&#xff1a; 组合问题&#xff1a;选取一个a之后&#xff0c;在bcdef中再去选取第二个&#xff0c;选取b之后在cdef中再选取第三个…。切割问题&#xff1a;切割一个a之后&…...

【C++】string类的基本使用

层楼终究误少年&#xff0c;自由早晚乱余生。你我山前没相见&#xff0c;山后别相逢… 文章目录一、编码&#xff08;ascll、unicode字符集、常用的utf-8编码规则、GBK&#xff09;1.详谈各种编码规则2.汉字在不同的编码规则中所占字节数二、string类的基本使用1.string类的本质…...

【第一章 - 绪论】- 数据结构(近八千字详解)

目录 一、 数据结构的研究内容 二、基本概念和术语 2.1 - 数据、数据元素、数据项和数据对象 2.2 - 数据结构 2.2.1 - 逻辑结构 2.2.2 - 存储结构 2.3 - 数据类型和抽象数据类型 三、抽象数据类型的表现与实现 四、算法和算法分析 4.1 - 算法的定义及特性 4.2 - 评价…...

QIfw制作软件安装程序

前言 Qt Installer Framework是Qt默认包的发布框架。它很方便,使用静态编译Qt制作而成。从Qt的下载地址中下载Qt Installer Framework,地址是:http://download.qt.io/official_releases/qt-installer-framework/ 。支持我们自定义一些我们需要的东西包括页面、交互等。 框…...

【C++】C++入门(上)

前言&#xff1a; C是在C语言的基础上不断添加东西形成的一门语言&#xff0c;在C语言的基础上引入了面向对象的思想。因此C既是面向对象的语言&#xff0c;也是面向过程的语言。因为C是以C语言为基础的&#xff0c;所以基本上C兼容所有的C语言。目前最常用的版本是C98和C11这两…...

5. Kimball维度建模常用术语及概念(一)

文章目录维度建模过程相关概念1. 收集业务需求与数据实现2. 协作维度建模研讨3. 四步骤维度设计过程4. 业务过程5. 粒度6. 描述环境的维度7. 用于度量的事实8. 维度模型事实表技术术语1. 事实表结构2. 可加、半可加、不可加事实3. 事实表中的空值4. 一致性事实5. 事务事实表6. …...

内核调试之Panic-Oops日志分析

这部分我们接着之前的思考&#xff0c;看看内核异常日志的分析。 1 Panic 调试 2 Oops调试 内核出现Panic或Oops错误&#xff0c;如何分析定位问题原因&#xff1f; 首先&#xff0c;保留现场&#xff0c;如下所示为一次非法虚拟地址访问错误。 EXT4-fs (sdc3): recovery c…...

论文解读 | [AAAI2020] 你所需要的是边界:走向任意形状的文本定位

目录 1、研究背景 2、研究的目的 3、方法论 3.1 Boundary Point Detection Network(BPDN) 3.2 Recognition Network 3.3 Loss Functions 4、实验及结果 论文连接&#xff1a;https://ojs.aaai.org/index.php/AAAI/article/view/6896 1、研究背景 最近&#xff0c;旨在…...

数据挖掘流程简单示例10min

数据挖掘流程简单示例10min 套路&#xff1a; 准备数据实现算法测试算法 任务1&#xff1a;亲和性分析 如果一个顾客买了商品X&#xff0c;那么他们可能愿意买商品Y衡量方法&#xff1a; 支持度support : 所有买X的人数 置信度confidence : 所有买X和Y的人数所有买X的人数…...

KDJB1200六相继电保护测试仪

一、概述 KDJB1200继电保护测试仪是在参照电力部颁发的《微机型继电保护试验装置技术条件(讨论稿)》的基础上&#xff0c;广泛听取用户意见&#xff0c;总结目前国内同类产品优缺点&#xff0c;充分使用现代新的的微电子技术和器件实现的一种新型小型化微机继电保护测试仪。可…...

从WEB到PWA 开发-发布-安装

见意如题&#xff01;本文主要来说说PWA开发&#xff01;作为一个前端程序员&#xff0c;在没有任何Android/IOS的开发情况下&#xff0c;想想我们有多少种方法来开发一个原生移动应用程序&#xff01;我们可以有非原生、混合开发&#xff0c;PWA等等手段。类似uniapp&#xff…...

FPGA纯vhdl实现MIPI CSI2 RX视频解码输出,OV13850采集,提供工程源码和技术支持

目录1、前言2、Xilinx官方主推的MIPI解码方案3、纯Vhdl方案解码MIPI4、vivado工程介绍5、上板调试验证6、福利&#xff1a;工程代码的获取1、前言 FPGA图像采集领域目前协议最复杂、技术难度最高的应该就是MIPI协议了&#xff0c;MIPI解码难度之高&#xff0c;令无数英雄竞折腰…...

《NFL橄榄球》:卡罗来纳黑豹·橄榄1号位

卡罗来纳黑豹&#xff08;英语&#xff1a;Carolina Panthers&#xff09;是一支位于北卡罗来纳州夏洛特的职业美式橄榄球球队。他们是国家美式橄榄球联合会的南区其中一支球队。他们与杰克逊维尔美洲虎在1995年加入NFL&#xff0c;成为扩充球队。 2018年球队市值为23亿美元&am…...

我说我为什么抽不到SSR,原来是这段代码在作祟...

本文是龚国玮所写&#xff0c;熊哥有所新增修改删减&#xff0c;原文见文末。 我说我为什么抽不到SSR&#xff0c;原来是加权随机算法在作祟 阅读本文需要做好心理准备&#xff0c;建议带着深究到底的决心和毅力进行学习&#xff01; 灵魂拷问 为什么有 50% 的几率获得金币&a…...

MySQL MGR 集群新增节点

前言 服务器规划现状&#xff08;CentOS7.x&#xff09; IP地址主机名部署角色192.168.x.101mysql01mysql192.168.x.102mysql02mysql192.168.x.103mysql03mysql192.168.x.104proxysql01proxysql、keepalived192.168.x.105proxysql02proxysql、keepalived 新增服务器IP&#x…...

【单目标优化算法】蜣螂优化算法(Dung beetle optimizer,DBO)(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【C++】类和对象入门必知

面向过程和面向对象的初步认识类的引入类的定义类的访问限定符封装类的作用域类的实例化类对象模型this指针C语言和C实现Stack的对比面向过程和面向对象的初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解…...

day38 动态规划 | 509、斐波那契数 70、爬楼梯 746、使用最小花费爬楼梯

题目 509、斐波那契数 斐波那契数&#xff0c;通常用 F(n) 表示&#xff0c;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)&#xff0c;其…...

2023年备考软考必须知道的6件事

不知不觉&#xff0c;距离2023年上半年软考也只有不到100天的时间了&#xff0c;报名入口也将在3月13日正式开通&#xff0c;你是正在犹豫是否参加考试? 还是已经开始着手准备复习? 关于软考考试你还有哪些疑问? 2023年备考软考必须知道的6件事&#xff0c;建议收藏&#xf…...

GLOG如何控制输出的小数点位数

1 问题 在小白的蹩脚翻译演绎型博文《GLOG从入门到入门》中&#xff0c;有位热心读者提问说&#xff1a;在保存日志时&#xff0c;浮点型变量的小数位数如何设置&#xff1f; 首先感谢这位“嘻嘻哈哈的地球人”赏光阅读了小白这不太通顺的博客文章&#xff0c;并提出了一个很…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

6.9-QT模拟计算器

源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

Docker、Wsl 打包迁移环境

电脑需要开启wsl2 可以使用wsl -v 查看当前的版本 wsl -v WSL 版本&#xff1a; 2.2.4.0 内核版本&#xff1a; 5.15.153.1-2 WSLg 版本&#xff1a; 1.0.61 MSRDC 版本&#xff1a; 1.2.5326 Direct3D 版本&#xff1a; 1.611.1-81528511 DXCore 版本&#xff1a; 10.0.2609…...