题目要求
1
2
3
4
5
6
| Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
|
现在有一个字符串s，将s分割为多个子字符串从而保证每个子字符串都是回数。问最少需要分割多少次。
思路一：HashMap缓存
这道题目的核心思想是动态编程，假设我们已经知道[0,1],[0,2]…[0,i-1]每个子字符串的最少分割数，那么我们可以得出[0,i]子字符串的最小分割数。我们只需要从第i个字符开始往回找所有可以和第i个字符构成回数,假设从第j个字符到第i个字符可以构成回数（0<=j<=i），那么以j作为分割线得到的最少分割数为cut[j-1]+1。我们只需要找到所有可以构成回数的j并且得出最小值即可。
刚开始，我选择利用hashmap记录所有可能构成回数的情况。即将字符作为key，将字符所在的下标列表作为value。这样每次遍历一个字符时，只需要从hashmap中找到该字符的所有下标并判断该子字符串是否是回数即可。
它有一个很明显的缺陷，就是当出现大量以单一字符构成的回数时，如aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaa会超时。很明显还有更好的存储中间结果的方式。
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
| Map<Character, List<Integer>> cache = new HashMap<Character, List<Integer>>();
public int minCut(String s) {
if(s==null || s.length()==0) return 0;
int[] minCut = new int[s.length()+1];
minCut[0] = -1;
for(int i = 0 ; i<s.length() ; i++){
char cur = s.charAt(i);
if(!cache.containsKey(cur)){
minCut[i+1] = minCut[i] + 1;
List<Integer> list = new ArrayList<Integer>();
list.add(i);
cache.put(cur, list);
}else{
int max = minCut[i] + 1;
List<Integer> values = cache.get(cur);
for(int index : values){
if(isPalindrome(s.substring(index, i+1))){
max = Math.min(max, minCut[index]+1);
}
}
minCut[i+1] = max;
values.add(i);
}
}
return minCut[s.length()];
}
public boolean isPalindrome(String subString){
if(subString.length()<=1) return true;
char[] sArray = subString.toCharArray();
int left = 0,
right = subString.length()-1;
while(left<right){
if(sArray[left] != sArray[right]){
return false;
}
left++;
right--;
}
return true;
}
|
思路二：存储中间的回数结果
这里我们采用二维数组的方式来存储中间的回数结果。我们会新建一个boolean[s.length][s.length] isPalindrome,其中isPalindrome[i][j]代表从i开始j结束的子数组是否是回数。再采用上面所说的方法，利用中间结果得出最小分割次数。
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
| public int minCut2(String s){
if(s==null || s.length()<=1) return 0;
int length = s.length();
boolean[][] isPalindrome = new boolean[length][length];
int[] result = new int[length];
char[] array = s.toCharArray();
for(int end = 0 ; end<length ; end++){
result[end] = end;
for(int start = end ; start>=0 ; start--){
if(array[start] == array[end]){
if(end-start<=2){
isPalindrome[start][end] = true;
}else{
isPalindrome[start][end] = isPalindrome[start+1][end-1];
}
}
if(isPalindrome[start][end]){
if(start==0){
result[end] = 0;
}else{
result[end] = Math.min(result[start-1]+1, result[end]);
}
}
}
}
return result[length-1];
}
|