Leetcode-131.Palindrome Partitioning [C++][Java]

目录

一、题目描述

二、解题思路

【C++】

【Java】


Leetcode-131.Palindrome Partitioninghttps://leetcode.com/problems/palindrome-partitioning/description/131. 分割回文串 - 力扣(LeetCode)131. 分割回文串 - 给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1:输入:s = "aab"输出:[["a","a","b"],["aa","b"]]示例 2:输入:s = "a"输出:[["a"]] 提示: * 1 <= s.length <= 16 * s 仅由小写英文字母组成https://leetcode.cn/problems/palindrome-partitioning/description/

一、题目描述

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.

二、解题思路

  • 时间复杂度:O(n⋅2^n)

  • 空间复杂度:O(n^2)

【C++】

class Solution {
private:void dfs(const string& s, int start, vector<string>& pat, vector<vector<string>>& res) {if (start == s.length()) {res.push_back(pat);}else {for (int i = start; i < s.length(); i++) {if (isPalindrome(s, start, i)) {pat.push_back(s.substr(start, i - start + 1));dfs(s, i + 1, pat, res);pat.pop_back();}}}}bool isPalindrome(const string& s, int l, int r) {while (l <= r) if (s[l++] != s[r--]) return false;return true;}public:vector<vector<string>> partition(string s) {vector<vector<string>> res;vector<string> pat;      dfs(s, 0, pat, res);return res;}
};

【Java】

class Solution {private void dfs(String s, int start, List<String> pat, List<List<String>> res) {if (start == s.length()) {res.add(new ArrayList<>(pat));}else {for (int i = start; i < s.length(); i++) {if (isPalindrome(s, start, i)) {pat.add(s.substring(start, i + 1));dfs(s, i + 1, pat, res);pat.remove(pat.size() - 1);}}}}private boolean isPalindrome(String s, int l, int r) {while (l <= r) if (s.charAt(l++) != s.charAt(r--)) return false;return true;}public List<List<String>> partition(String s) {List<List<String>> res = new ArrayList<>();List<String> pat = new ArrayList<>();dfs(s, 0, pat, res);return res;}
}

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

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

相关文章

InternVL:论文阅读 -- 多模态大模型(视觉语言模型)

更多内容&#xff1a;XiaoJ的知识星球 文章目录 InternVL: 扩展视觉基础模型与通用视觉语言任务对齐1.概述2.InternVL整体架构1&#xff09;大型视觉编码器&#xff1a;InternViT-6B2&#xff09;语言中间件&#xff1a;QLLaMA。3&#xff09;训练策略&#xff08;1&#xff09…

【AWS入门】AWS云计算简介

【AWS入门】AWS云计算简介 A Brief Introduction to AWS Cloud Computing By JacksonML 什么是云计算&#xff1f;云计算能干什么&#xff1f;我们如何利用云计算&#xff1f;云计算如何实现&#xff1f; 带着一系列问题&#xff0c;我将做一个普通布道者&#xff0c;引领广…

二分算法刷题

1. 初识 总结&#xff1a;二分算法题的细节非常多&#xff0c;容易写出死循环。使用算法的条件不一定是数组有序&#xff0c;而是具有“二断性”&#xff1b;模板三种后面会讲。 朴素二分二分查找左端点二分查找右端点 2. 朴素二分 题目链接&#xff1a;704. 二分查找 - 力扣…

itsdangerous加解密源码分析|BUG汇总

这是我这两天的思考 早知道密码学的课就不旷那么多了 纯个人见解 如需转载&#xff0c;标记出处 目录 一、官网介绍 二、事例代码 源码分析&#xff1a; 加密函数dump源码使用的函数如下&#xff1a; 解密 ​编辑 ​编辑 关于签名&#xff1a; 为什么这个数字签名没有…

深度解析React Native底层核心架构

React Native 工作原理深度解析 一、核心架构&#xff1a;三层异构协作体系 React Native 的跨平台能力源于其独特的 JS层-Shadow层-Native层 架构设计&#xff0c;三者在不同线程中协同工作&#xff1a; JS层 运行于JavaScriptCore&#xff08;iOS&#xff09;或Hermes&…

前端内存优化实战指南:从内存泄漏到性能巅峰

前端内存优化实战指南&#xff1a;从内存泄漏到性能巅峰 一、内存问题引发的场景 1.1 典型内存灾难现场 // 经典内存泄漏示例 const zombieElements new Set();function createLeak() {const div document.createElement(div);zombieElements.add(div); // 元素永不释放div…

【工作记录】pytest使用总结

1、 fixture夹具 可参考&#xff1a; python3.x中 pytest之fixture - 漂泊的小虎 - 博客园 fixture是指夹具&#xff08;把用例夹在中间&#xff09;&#xff0c;它包括前置工作和后置工作&#xff0c;前置是用例代码的准备阶段&#xff0c;后置是用例执行之后的清理阶段,用…

C++基础笔记

1. C关键字 这个不多说&#xff0c;以后接触得到&#xff0c;但这里做个总结&#xff1a; 2. 命名空间 一般类型&#xff1a; namespace Xianyu {// 命名空间中可以定义变量/函数/类型int rand 10;int Add(int left, int right){return left right;}struct Node{struct No…

生活中的可靠性小案例12:类肤材质老化发粘问题

我一直觉得我买的某品牌车载吸尘器很好用&#xff0c;用了几年&#xff0c;目前性能也是杠杠的。然而它现在有个最大的问题&#xff0c;就是表面发粘了&#xff0c;用起来粘手&#xff0c;非常不舒服。 这一类问题在生活中不少见&#xff0c;尤其是一些用了类肤材质涂层的物件。…

黑马node.js教程(nodejs教程)——AJAX-Day01-04.案例_地区查询——查询某个省某个城市所有地区(代码示例)

文章目录 代码示例效果 代码示例 axiosTest.html <!DOCTYPE html> <!-- 文档类型声明&#xff0c;告诉浏览器这是一个HTML5文档 --> <html lang"en"> <!-- HTML根元素&#xff0c;设置文档语言为英语 --><head> <!-- 头部区域&am…

Ollama+OpenWebUI本地部署大模型

OllamaOpenWebUI本地部署大模型 前言Ollama使用Ollama安装Ollama修改配置Ollama 拉取远程大模型Ollama 构建本地大模型Ollama 运行本地模型&#xff1a;命令行交互Api调用Web 端调用 总结 前言 Ollama是一个开源项目&#xff0c;用于在本地计算机上运行大型语言模型&#xff0…

【NeurIPS 2024】LLM-ESR:用大语言模型破解序列推荐的长尾难题

标题期刊年份关键词LLM-ESR: Large Language Models Enhancement for Long-tailed Sequential RecommendationNeurIPS2024Large Language Models, Sequential Recommendation, Long-tailed &#x1f4da;研究背景 在电商和社交媒体的世界里&#xff0c;序列推荐系统&#xff…

C语言_数据结构总结9:树的基础知识介绍

1. 树的基本术语 - 祖先&#xff1a;考虑结点K&#xff0c;从根A到结点K的唯一路径上的所有其它结点&#xff0c;称为结点K的祖先。 - 子孙&#xff1a;结点B是结点K的祖先&#xff0c;结点K是B的子孙。结点B的子孙包括&#xff1a;E,F,K,L。 - 双亲&#xff1a;路径上…

Android 14 Telephony 网络选择功能介绍

一、总体介绍 (一)功能 手动搜网的流程:用户通过UI触发,调用TelephonyManager的API,比如startNetworkScan,然后这个请求会传递到RIL层,通过AT命令与基带通信,进行网络扫描。结果返回后,经过TelephonyRegistry通知应用层。中间可能涉及IPC,比如Binder通信,因为应用和…

系统思考全球化落地

感谢加密货币公司Bybit的再次邀请&#xff0c;为全球团队分享系统思考课程&#xff01;虽然大家来自不同国家&#xff0c;线上学习的形式依然让大家充满热情与互动&#xff0c;思维的碰撞不断激发新的灵感。 尽管时间存在挑战&#xff0c;但我看到大家的讨论异常积极&#xff…

位运算(基础算法)

按位与AND&#xff08; & &#xff09; 只有当两个位都为1时&#xff0c;结果才为1,否则为0。结果不会变大 按位或 OR&#xff08; | &#xff09; 只有当两个位中有一个为1时&#xff0c;结果才为1,否则为0。结果不会变小 按位异或 XOR &#xff08; ^ &#xff09; 只…

规模效应的三重边界:大白话解读-deepseek为例

前言&#xff1a;当Scaling Laws遇见边际递减效应 在人工智能的狂飙突进中&#xff0c;大语言模型如同不断膨胀的星体&#xff0c;吞噬着海量算力与数据。OpenAI于2020年揭开的Scaling Laws&#xff0c;曾为这场盛宴指明方向&#xff1a;模型性能随参数规模&#xff08;N&…

力扣143重排链表

143. 重排链表 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为&#xff1a; L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的…

wow-rag:task3-初步体验问答引擎

做RAG需要自己准备一个txt文档&#xff0c;新建一个docs文件夹&#xff0c;放进去。例如&#xff0c;这里放了一个./docs/问答手册.txt # 从指定文件读取&#xff0c;输入为List from llama_index.core import SimpleDirectoryReader,Document documents SimpleDirectoryRead…

bgp服务器是什么意思

一、基础概念 ‌BGP服务器‌&#xff08;Border Gateway Protocol Server&#xff09;指通过 ‌边界网关协议&#xff08;BGP&#xff09;‌ 实现 ‌多运营商线路智能调度‌ 的服务器&#xff0c;能够自动选择最优路径连接不同网络&#xff08;如电信、联通、移动&#xff09;…