问题描述
给定一个字符串，要求找出最小分割次数，使分割后的字符串都是回文字符串。题目链接：**点我**
样例输入输出
输入：aaa
输出：0
输入：aab
输出：1
问题解法
使用动态规划进行求解。用 dp[i] 表示字符串中 0~i 构成的子字符串所需要的最小分割次数。则动态转移方程为 如果 0 到 i 组成的子字符是回文字符串，则 dp[i] = 0，否则 dp[i] = min(dp[i], dp[k] + 1)(k 从 0 到 i - 1)（其中，k + 1 到 i 组成的子字符串是一个回文字符串）。至于判断从 i 到 j 构成的字符串是否是回文字符串，同样可以用动态规划进行求解，其动态转移方程为 dp[i][j] = dp[i + 1][j - 1] && a[i + 1] == a[j - 1]。这样在后续进行比较中就能直接获取到对应的值而不用每次都进行回文串的判断，减少时间消耗。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution
{
public int minCut(String s)
{
boolean[][] palindromeArray = new boolean[s.length()][s.length()];
handlePalindromeArray(s, palindromeArray);
int[] minCuts = new int[s.length()];
Arrays.fill(minCuts, Integer.MAX_VALUE);
for (int i = 0; i < s.length(); i++)
{
if (palindromeArray[0][i])
{
minCuts[i] = 0;
continue;
}
for (int j = 0; j < i; j++)
{
if (palindromeArray[j + 1][i] && (minCuts[j] + 1) < minCuts[i])
{
minCuts[i] = minCuts[j] + 1;
}
}
}
return minCuts[s.length() - 1];
}
private void handlePalindromeArray(String str, boolean[][] dp)
{
for (int j = 0; j < str.length(); j++)
{
for (int i = j; i >= 0; i--)
{
if (i == j || i == j - 1)
{
dp[i][j] = str.charAt(i) == str.charAt(j);
}
else
{
dp[i][j] = dp[i + 1][j - 1] && (str.charAt(i) == str.charAt(j));
}
}
}
}
}
|