LeetCode_回溯_动态规划_中等_131.分割回文串
2023-09-27 14:25:46 时间
1.题目
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文串 。返回 s 所有可能的分割方案。
回文串是正着读和反着读都一样的字符串。
示例 1:
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2:
输入:s = “a”
输出:[[“a”]]
提示:
1 <= s.length <= 16
s 仅由小写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/palindrome-partitioning
2.思路
(1)回溯_动态规划
思路参考本题官方题解。
相关题目:
LeetCode_动态规划_中等_5.最长回文子串
LeetCode_双指针_简单_234.回文链表
LeetCode_贪心算法_简单_409.最长回文串
LeetCode_动态规划_中等_516.最长回文子序列
LeetCode_字符串_中等_647. 回文子串
LeetCode_双指针_简单_1332.删除回文子序列
3.代码实现(Java)
//思路1————回溯_动态规划
class Solution {
//dp[i][j] 表示 s[i...j] 是否为回文串
boolean[][] dp;
//res 保存最终的结果
List<List<String>> res = new ArrayList<>();
//path 保存回溯过程中的符合条件的结果
List<String> path = new ArrayList<>();
//字符串长度
int length;
public List<List<String>> partition(String s) {
length = s.length();
dp = new boolean[length][length];
for (int i = 0; i < length; i++) {
Arrays.fill(dp[i], true);
}
for (int i = length - 1; i >= 0; i--) {
for (int j = i + 1; j < length; j++) {
dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
}
}
backtrace(s, 0);
return res;
}
public void backtrace(String s, int i) {
if (i == length) {
res.add(new ArrayList<String>(path));
return;
}
for (int j = i; j < length; j++) {
if (dp[i][j]) {
path.add(s.substring(i, j + 1));
backtrace(s, j + 1);
path.remove(path.size() - 1);
}
}
}
}
相关文章
- JS Leetcode 70. 爬楼梯 题解分析,斐波那契数列与动态规划
- LeetCode动态规划基础题-子字符串问题(13题)
- LeetCode动态规划基础题-打家劫舍
- 198、【动态规划】leetcode ——983. 最低票价:记忆化搜索(C++版本)
- 181、【动态规划】leetcode ——72. 编辑距离(C++版本)
- 170、【动态规划】leetcode ——188. 买卖股票的最佳时机 IV:二维数组+一维数组 (C++版本)
- 158、【动态规划】leetcode ——518. 零钱兑换 II:二维数组+一维滚动数组(C++版本)
- 148、【动态规划】leetcode ——63. 不同路径 II:递归法+迭代法(C++版本)
- 146、【动态规划】leetcode ——746. 使用最小花费爬楼梯:递归法+迭代法(C++版本)
- 145、【动态规划】leetcode ——70. 爬楼梯:暴力法+动态规划(C++版本)
- 【算法/动态规划】leetcode刷题路线(持续更新)
- 【leetcode】230: 二叉搜索树中第K小的元素