對一個(gè)字符串按照回文進(jìn)行分割，例如aba|b|bbabb|a|b|aba就是字符串a(chǎn)babbbabbababa的一個(gè)回文分割，每一個(gè)字串都是一個(gè)回文。請找到可以分割的最少的字串?dāng)?shù)。例如：
1. ababbbabbababa最少4個(gè)字符串，分割三次：a|babbbab|b|ababa
2. 如果字符串整體是回文，則需要0次分割，最少1個(gè)字符串
分析：
遞歸方程為：f(i) = MIN(f(j - 1) + 1), map[j][i] == true, 0<=j<i，其中f(i)為以第i個(gè)字符結(jié)尾的字符串的最小切割次數(shù)，map數(shù)組用來記錄s[i][j]是否是對稱的。實(shí)現(xiàn)代碼如下：
1 public class Solution {
2 public int minPalindromePartition(String s) {
3 int length = s.length();
4 boolean[][] map = new boolean[length][length];
5 int[] record = new int[length];
6 for (int k = 0; k < length; k++) {
7 record[k] = k;
8 }
9 for (int offset = 0; offset < length; offset++) {
10 for (int i = 0, j = i + offset; i < length - offset; i++, j++) {
11 if (i == j || (s.charAt(i) == s.charAt(j) && (j - i == 1 || map[i + 1][j - 1]))) {
12 map[i][j] = true;
13 }
14 }
15 }
16 for (int i = 1; i < length; i++) {
17 for (int j = 0; j < i; j++) {
18 if (map[j][i]) {
19 if (j > 0) {
20 record[i] = Math.min(record[i], record[j - 1] + 1);
21 } else {
22 record[i] = 0;
23 }
24 }
25 }
26 }
27 return record[length - 1];
28 }
29 }