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.
这道题做了比较长的时间,尝试了好多次,总是超时。这道题递归的思路很明显,但是如果只是简单的使用递归,由于会重复计算很多的子问题,必然会超时。所以我一开始就尝试了使用DP。
第一次尝试的时候,想出的方案是3维的DP:对于一个以i为起点,长度为j的子字符串s[i...i + j - 1],让min(i,j)表示所含回文的最小数量。那么min(i,j) =:
1) 1, 如果字符串本身是回文;
2) min(min(i, k) + min(k, j - k), min(i, j)), 如果对于所有的k,0 < k < j,这个时候min(i, j)的初始值为j,即为最坏情况:当字符串完全拆成单个字符,所含回文个数即字符串长度。
最后所求的最小切割数就是整个字符串所含的回文的最小数减去1。
private boolean isValid(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (s.charAt(i) != s.charAt(j)) { return false; } else { i++; j--; } } return true; } public int minCut(String s) { int length = s.length(); // min[i][j] represents the minimum number of composed palindromes for // the string starts at i and has a length of j int min[][] = new int[length][length + 1]; for (int j = 1; j <= length; j++) { for (int i = 0; i < length; i++) { if (i + j <= length) { if (isValid(s.substring(i, i + j))) { min[i][j] = 1; continue; } else { min[i][j] = j; for (int k = 1; k < j; k++) { min[i][j] = Math.min(min[i][k] + min[k][j - k], min[i][j]); if (min[i][j] == 2) break; } } } else { break; } } } return min[0][length] - 1; }
以上代码还是经过几次尝试后优化过了的,已经在好几个部分插入了continue和break,以避免不必要的计算。例如当子字符串本身为回文,或者本身不为回文但可以被拆分成两个回文,就已经达到了当前的最优情况,不必再继续搜索了。但是还是超时啊。。。。
于是开始了第二次尝试,目标是从根本上减少DP的时间复杂度,因为O(N^3)的时间复杂度还是实在太高了。于是想到了一个O(N^2)的方案:
让min[i]表示从字符串最左边开始,到下标i结束的子字符串,所构成的回文的最小数目。那么min[i]有三种可能值:
1)当子字符串本身为回文,那么min[i]=1;
2)当子字符串本身不是回文的时候,令0<= j < i,
如果s[j + 1...i]为回文,那么min[i]=min[j] + 1;否则,min[i]=min[j] + i - j +1(当成余下部分全部拆成单个字符的最坏情况)。
所求就是min[N] - 1了。注意代码里我还是加了起优化作用的continue和break,以减少不必要的计算。
private boolean isValid(String s) { int i = 0, j = s.length() - 1; while (i < j) { if (s.charAt(i) != s.charAt(j)) { return false; } else { i++; j--; } } return true; } public int minCut(String s) { int length = s.length(); int min[] = new int[length]; min[0] = 1; for (int i = 1; i < length; i++) { if (isValid(s.substring(0, i + 1))) { min[i] = 1; continue; } else { // the worst case: partition the word into single letters min[i] = i + 1; } // j is the end of the first part for (int j = 0; j < i; j++) { if (isValid(s.substring(j + 1, i + 1))) { min[i] = Math.min(min[i], min[j] + 1); if (min[i] == 2) break; } // treat the remaining part as all single characters else { min[i] = Math.min(min[i], min[j] + i - j + 1); if (min[i] == 2) break; } } } return min[length - 1] - 1; }
这次尝试终于过了!网上搜了一下,发现还可以更加优化。因为其实在多次判断回文的过程中还是引入了不少重复计算,所以在可以将判断回文的时候函数去掉,换成一个二维表,于是判断回文再也不用将整个输入的字符串再扫一遍,而是转化为了一个简单的查看表格内某元素的操作。所以把之前代码里的isValid函数用一个DP建立的二维表替换掉了。
public int minCut(String s) { int length = s.length(); // make the palindrome validation become a look-up operation boolean valid[][] = new boolean[length][length]; // valid[i][j] represents the s[i...j] is a palindrome or not for (int i = 1; i <= length; i++) { for (int j = 0; j + i <= length; j++) { if (i == 1) valid[j][j + i - 1] = true; else if (i == 2) valid[j][j + i - 1] = s.charAt(j) == s.charAt(j + 1); else valid[j][j + i - 1] = (s.charAt(j) == s.charAt(j + i - 1)) && valid[j + 1][j + i - 2]; } } // min[i] represents the minimum number of composed palindromes for // the string starts at 0 and ends at i (inclusive) int min[] = new int[length]; min[0] = 1; for (int i = 1; i < length; i++) { if (valid[0][i]) { min[i] = 1; continue; } else { // the worst case: partition the word into single letters min[i] = i + 1; } // j is the end of the first part for (int j = 0; j < i; j++) { if (valid[j + 1][i]) { min[i] = Math.min(min[i], min[j] + 1); if (min[i] == 2) break; } // treat the remaining part as all single characters else { min[i] = Math.min(min[i], min[j] + i - j + 1); if (min[i] == 2) break; } } } return min[length - 1] - 1; }