131.分割回文串

在这里插入图片描述

// 定义一个名为Solution的类
class Solution {

    // 声明一个成员变量,用于存储所有满足条件的字符串子序列划分结果
    List<List<String>> lists = new ArrayList<>(); 

    // 声明一个成员变量,使用LinkedList实现的双端队列,用于临时存储当前的回文子串
    Deque<String> deque = new LinkedList<>();

    // 公共方法:partition,输入一个字符串s,返回所有可能的回文子序列划分结果
    public List<List<String>> partition(String s) {
        // 调用回溯法进行字符串划分处理
        backTracking(s, 0);
        // 返回所有找到的回文子序列划分集合
        return lists;
    }

    // 私有辅助方法:backTracking,采用回溯算法遍历字符串s的所有可能划分
    private void backTracking(String s, int startIndex) {
        // 当起始位置大于等于字符串s的长度时,说明已经找到一组合法的回文子序列划分,将其添加到结果集中
        if (startIndex >= s.length()) {
            // 将deque中的回文子串列表复制一份添加到结果集lists中
            lists.add(new ArrayList<>(deque));
            return;
        }

        // 遍历从startIndex开始到字符串末尾的所有可能划分点
        for (int i = startIndex; i < s.length(); i++) {
            // 判断从startIndex到i(含)之间的子串是否为回文串
            if (isPalindrome(s, startIndex, i)) {
                // 若是回文串,则将该子串添加到deque中
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                // 若不是回文串,则跳过本次循环继续尝试下一个子串
                continue;
            }

            // 继续递归处理剩余部分字符串,同时确保不会重复处理已划分的部分
            backTracking(s, i + 1);

            // 回溯:在尝试完当前子串之后,将其从deque中移除,以便于尝试下一种可能的划分方式
            deque.removeLast();
        }
    }

    // 私有辅助方法:isPalindrome,用于判断给定索引范围内的子串是否为回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        // 双指针从两端向中间遍历,比较字符是否相等
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                // 如果发现有不相等的字符,则立即返回false,表示该子串不是回文串
                return false;
            }
        }
        // 所有字符都匹配成功,说明子串是回文串,返回true
        return true;
    }
}

上述代码定义了一个名为 Solution 的类,该类用于解决一个问题:将一个输入字符串 s 划分成多个子串,使得这些子串都是回文串。通过回溯算法,找出所有可能的回文子序列划分,并将结果以 List<List> 的形式返回。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Objective -- C】—— 自引用计数

【Objective -- C】—— 自引用计数 一. 内存管理/自引用计数1.自引用计数2.内存管理的思考方式自己生成的对象&#xff0c;自己持有非自己生成的对象&#xff0c;自己也能持有不再需要自己持有的对象时释放无法释放非自己持有的对象 3.alloc/retain/release/dealloc实现4. aut…

力扣--滑动窗口438.找到字符串中所有字母异位词

思路分析&#xff1a; 使用两个数组snum和pnum分别记录字符串s和p中各字符出现的次数。遍历字符串p&#xff0c;统计其中各字符的出现次数&#xff0c;存储在pnum数组中。初始化snum数组&#xff0c;统计s的前m-1个字符的出现次数。从第m个字符开始遍历s&#xff0c;通过滑动窗…

《YOLO5Face: Why Reinventing a Face Detector》为什么要重塑人脸检测器论文阅读

正好周末的时间天气也不错出去走走精神不错&#xff0c;回来读一篇论文这个论文之前查资料的时候看到的但是没有完整看下&#xff0c;今天正好花点时间整体看一下&#xff0c;下面是我自己阅读过程中使用翻译软件结合自己理解的阅读记录&#xff0c;感兴趣的话可以看下&#xf…

知识图谱 | 2023年图书馆学、情报学CSSCI期刊论文主题透视

数据来源 检索平台来源期刊年份有效数据中国知网大学图书馆学报国家图书馆学刊情报科学情报理论与实践情报学报情报杂志情报资料工作数据分析与知识发现图书馆建设图书馆论坛图书馆学研究图书馆杂志图书情报工作图书情报知识图书与情报现代情报信息资源管理学报中国图书馆学报2…

性能测试高阶内容:了解TPS和RT之间关系

引言 在开始今天的内容讲解之前&#xff0c;我们应该回顾一下&#xff0c;在我的全链路压测专栏中的第一篇&#xff0c;我就已经介绍了当前的性能测试在互联网企业中的重要性&#xff0c;已经性能在互联网行业中的占比是多少。 这个时候是不是会有同学问我&#xff0c; 你已经…

JVM-1

目录 1.基础知识 1.栈 2.本地方法栈 3.程序计数器 4.堆 5.方法区 6.JVM内存可见性 2.虚拟机类加载机制 1.加载 2.验证 3.准备 4.解析 5.初始化 6.使用 7.卸载 1.基础知识 JVM内存模型&#xff08;5种&#xff09;&#xff1a;栈&#xff0c;本地方法栈&#xff…

Java项目:44 ssm003在线医疗服务系统+jsp(含文档)

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 主要功能 前台登录&#xff1a; 注册用户&#xff1a;用户名、密码、姓名、联系电话 注册医生&#xff1a;医生工号、密码、医生姓名、职称、联系电话…

【Python】专栏文章索引

为了方便 快速定位 和 便于文章间的相互引用等 作为一个快速准确的导航工具 Python 目录&#xff1a; &#xff08;一&#xff09;装饰器函数 &#xff08;二&#xff09;牛客网—软件开发-Python专项练习 &#xff08;三&#xff09;time模块

数据结构与算法第三套试卷

1.删除链表节点 **分析&#xff1a;**首先用指针变量q指向结点A的后继结点B&#xff0c;然后将结点B的值复制到结点A中&#xff0c;最后删除结点B。 2.时间复杂度的计算 **分析&#xff1a;**当涉及嵌套循环的时候&#xff0c;我们可以直接分析内层循环即可&#xff0c;看内…

猫头虎分享已解决Bug || 批处理错误:BatchJobFailure, ProcessingDelay

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

太阳辐射环境模拟系统系统

太阳辐射环境模拟系统是一种高度专业化的设备&#xff0c;用于模拟太阳光的全谱段辐射&#xff0c;包括紫外线、可见光和红外线。这种系统的核心功能是在实验室条件下复制太阳的辐射条件&#xff0c;以评估材料、产品或设备在实际太阳辐射影响下的性能和耐久性。 应用领域&…

“比特币深夜冲破7万美元”!华尔街押注比特币:究竟是牛市墙头草,还是加密真信徒?

比特币ETF&#xff0c;使此次加密牛市与以往的繁荣、萧条周期截然不同。以往的周期往往由热衷风险的投机者以及最终崩盘的加密项目所驱动&#xff0c;例如无实物资产支持的加密货币借贷&#xff0c;以及一地鸡毛的ICO热潮。而现在&#xff0c;传统金融已经与加密世界联姻&#…

前端手册-实现挂坠灯笼效果

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…

专题一 - 双指针 - leetcode 202. 快乐数 | 简单难度

leetcode 202. 快乐数 leetcode 202. 快乐数 | 简单难度1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理3. 时间复杂度 3. 代码实现4. 知识与收获 leetcode 202. 快乐数 | 简单难度 1. 题目详情 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」…

linux守护程序

概述 周末还要加班写代码&#xff0c;偷个懒发个刚刚写的守护进程&#xff0c;有一个小bug懒得处理&#xff0c;急着要用&#xff0c;发出来记录一下成果。 守护程序 网上很多介绍的&#xff0c;大家有兴趣自己去查查 上酸菜 #include <stdio.h> #include <stdli…

代码随想录刷题笔记-Day32

1. 最大子序和 53. 最大子数组和https://leetcode.cn/problems/maximum-subarray/ 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组&#xff1a;是数组中的一个连续…

Java学习笔记NO.18

T1.理工超市 &#xff08;1&#xff09;题目描述 编写一个程序&#xff0c;设计理工超市功能菜单并完成注册和登录功能的实现。显示完菜单后&#xff0c;提示用户输入菜单项序号。当用户输入<注册>和<登录>菜单序号时模拟完成注册和登录功能&#xff0c;最后提示…

多态的原理

通过监视可以发现&#xff0c;基类和子类的虚表指针指向的是不同的虚表&#xff08;监视窗口可以证实&#xff09;&#xff0c;而且虚表里面的函数地址也是不一样的。这就符合我们的预期了&#xff0c;因为多态的调用的时候&#xff0c;就是通过虚表指针去找到对应虚表里面的虚…

蓝桥杯练习系统(算法训练)ALGO-981 过河马

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 在那个过河卒逃过了马的控制以超级超级多的走法走到了终点之后&#xff0c;这匹马表示它不开心了……   于是&#xff0c…

[2024-03-09 19:55:01] [42000][1067] Invalid default value for ‘create_time‘【报错】

这个错误可能是因为你的 MySQL 数据库版本不支持 CURRENT_TIMESTAMP 作为默认值。在一些早期版本中&#xff0c;MySQL 对 TIMESTAMP 类型字段的默认值设置有限制&#xff0c;只允许使用特定的常量值&#xff08;如 0000-00-00 00:00:00 或 CURRENT_TIMESTAMP()&#xff09;。如…