132. Palindrome Partitioning II

Bertha 。 2022-02-15 13:41 265阅读 0赞
  1. Given a string s, partition s such that every substring of the partition is a palindrome.
  2. Return the minimum cuts needed for a palindrome partitioning of s.
  3. Example:
  4. Input: "aab"
  5. Output: 1
  6. Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

本题可以看成一个动态规划题目。有以下两点可作为递推条件(cut[i]表示s.subString(0, i+1)满足题意的分割次数):

  1. 1cut\[i\]的值为当0 <= j <= i时,cut\[j\]的最小值加1
  2. 2,如果s.subString(j, i+1)是回文字符串且s.charAt(j-1)==s.charAt(i+1),则s.subString(j-1, i+2)也是回文字符串。
  3. public int minCut(String s) {
  4. char[] c = s.toCharArray();
  5. int n = c.length;
  6. int[] cut = new int[n];//cut[i]表示s.subString[i]达到题目要求的最小分割次数
  7. boolean[][] isPalinized = new boolean[n][n];//isPalinized[i][j]判断c[i]...c[j]组成的字符串是否是回文字符串
  8. for(int i = 0; i < n; ++i) {
  9. int min = i;//min等会赋值给cut[i],此时最大分割次数为i次
  10. for(int j = 0; j <= i; ++j) {
  11. if(c[j] == c[i] && (j + 1 > i - 1/**表示j + 1 == i这种情况**/ || isPalinized[j+1][i-1])) {
  12. isPalinized[j][i] = true;
  13. min = j == 0 ? 0/**表示s.subString(0, i+1)是回文的,即0次分割就能达到题目要求**/ : Math.min(min, cut[j-1] + 1/**s.subString(0, i+1)中,s.subString(j, i+1)是回文字符串所以此次结果为cut[j-1]+1**/)/**如上所说,min要赋值给cut[i],所以对所有情况,更新min**/;
  14. }
  15. }
  16. cut[i] = min;
  17. }
  18. return cut[n-1];
  19. }

发表评论

表情:
评论列表 (有 0 条评论,265人围观)

还没有评论,来说两句吧...

相关阅读