大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说Dynamic Programming学习笔记 (19) – 分割回文串 (力扣# 131),希望您对编程的造诣更进一步.
分割回文串使回文子串问题中较难的一个题面，题面为：
给定一个长度为N的字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
实例：
s = "aab"
答案: {{"a","a","b"}和{"aa","b"}}
解题思路：
我们首先使用回文子串问题的解法找到所有的回文子串，然后定义一个DP表达式F(k)，其中k是字串数组的下标，F(k)返回的是从k到N的子串可以分割而成的所有回文串的列表，F(1)返回的就是问题的最终答案。计算F(k)的过程是从k开始逐一找到从k开始的回文串，设定回文串的结束下标是i，我们可以通过F(i + 1)得到从i到N的的所有回文串的列表，而F(k)就是将s[i : j]添加到F(i + 1)中的每一项的头部后所形成的新的列表。
Java代码如下：
class Solution {
public List<List<String>> partition(String s) {
char[] chars = s.toCharArray();
int N = chars.length;
boolean[][] dp = new boolean[N + 1][N + 1];
for (int i = N; i >= 1; i --) {
dp[i][i] = true;
for (int j = i + 1; j <= N; j ++) {
if ((chars[i - 1] == chars[j - 1])) {
if ( j - i <= 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
}
}
List[] dp2 = new List[N + 1];
for (int k = N; k >= 1; k --) {
List<List<String>> result = new ArrayList<>();
for (int i = k; i <= N; i ++) {
if (dp[k][i]) {
String palindrome = s.substring(k - 1, i);
List dpValue = i < N ? dp2[i + 1] : null;
if (dpValue != null) {
for (int x = 0; x < dpValue.size(); x ++) {
List<String> item = new ArrayList();
item.add(palindrome);
item.addAll((List<String>) dpValue.get(x));
result.add(item);
}
} else {
result.add(Arrays.asList(palindrome));
}
}
}
dp2[k] = result;
}
return dp2[1];
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/13165.html
