分割字符串
131. 分割回文串
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
方法一：回溯+动态规划
需要求出字符串 $s$ 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。
我们可以将字符串 $s$ 的每个子串 $s[i..j]$ 是否为回文串预处理出来，使用动态规划即可。设 $f(i, j)$ 表示 $s[i..j]$是否为回文串，那么有状态转移方程：
其中 $\wedge$ 表示逻辑与运算，即 $s[i..j]$ 为回文串，当且仅当其为空串（$i>j$），其长度为 1（$i=j$），或者首尾字符相同且 $s[i+1..j-1]$ 为回文串。
预处理完成之后，我们只需要 $O(1)$ 的时间就可以判断任意 $s[i..j]$是否为回文串了。
代码
public List<List<String>> partition(String s) {
List<List<String>> ans = new ArrayList<>();
List<String> list = new ArrayList<>();
int length = s.length();
boolean[][] 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];
}
}
dfsForPartition(dp, s, ans, list, 0);
return ans;
}
private void dfsForPartition(boolean[][] dp, String s, List<List<String>> ans, List<String> list, int curr) {
if (curr == s.length()) {
ans.add(new ArrayList<>(list));
return;
}
for (int i = curr; i < s.length(); i++) {
if (dp[curr][i]) {
list.add(s.substring(curr, i + 1));
dfsForPartition(dp, s, ans, list, i + 1);
list.remove(list.size() - 1);
}
}
}
方法二：回溯+记忆化搜索
class Solution {
int[][] f;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
f = new int[n][n];
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (isPalindrome(s, i, j) == 1) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
// 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
public int isPalindrome(String s, int i, int j) {
if (f[i][j] != 0) {
return f[i][j];
}
if (i >= j) {
f[i][j] = 1;
} else if (s.charAt(i) == s.charAt(j)) {
f[i][j] = isPalindrome(s, i + 1, j - 1);
} else {
f[i][j] = -1;
}
return f[i][j];
}
}
132. 分割回文串 II
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a"
输出：0
示例 3：
输入：s = "ab"
输出：1
方法：动态规划
设 $f[i]$ 表示字符串的前缀 $s[0..i]$ 的最少分割次数。要想得出 $f[i]$ 的值，我们可以考虑枚举 $s[0..i]$分割出的最后一个回文串，这样我们就可以写出状态转移方程：
即我们枚举最后一个回文串的起始位置 $j+1$，保证 $s[j+1..i]$ 是一个回文串，那么 $f[i]$ 就可以从 $f[j]$ 转移而来，附加 $1$ 次额外的分割次数。
另外：当 $s[o…i]$ 本身就是一个回文串的时候，$f[i]=0$。
class Solution {
public int minCut(String s) {
int length = s.length();
boolean[][] 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];
}
}
int[] ans = new int[length];
Arrays.fill(ans, Integer.MAX_VALUE);
for (int i = 0; i < length; i++) {
if (dp[0][i]) {
ans[i] = 0;
} else {
for (int j = 0; j < i; j++) {
if (dp[j + 1][i]) {
ans[i] = Math.min(ans[i], ans[j] + 1);
}
}
}
}
return ans[length - 1];
}
}