LeetCode 131. Palindrome Partitioning
2022/6/14 23:23:11
本文主要是介绍LeetCode 131. Palindrome Partitioning,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode 131. Palindrome Partitioning (分割回文串)
题目
链接
https://leetcode.cn/problems/palindrome-partitioning/
问题描述
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
提示
1 <= s.length <= 16
s 仅由小写英文字母组成
思路
回溯法,采用截取字符串来判断回文。
复杂度分析
时间复杂度 O(n2) 空间复杂度 O(n)
代码
Java
LinkedList<String> path = new LinkedList<>(); List<List<String>> ans = new ArrayList<>(); public List<List<String>> partition(String s) { trace(s, 0); return ans; } public void trace(String s, int index) { if (index >= s.length()) { ans.add(new ArrayList<>(path)); return; } for (int i = index + 1; i <= s.length(); i++) { String tmp = s.substring(index, i); if (is(tmp)) { path.add(tmp); trace(s, i); path.removeLast(); } } } public boolean is(String s) { for (int i = 0, j = s.length() - 1; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; }
这篇关于LeetCode 131. Palindrome Partitioning的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain