P220 回文分割需要的最少分割次数

描述#

这个题目说的是，给你一个字符串 s，你要计算出将 s 分割成回文子串所需要的最少分割次数。

比如说，给你的字符串是：
"abc"
那你至少要分割两次，得到回文子串：
["a", "b", "c"]
因此你要返回的最少分割次数是 2。
再比如说，给你的字符串是：
"aab"
那你只需要分割一次，得到回文子串：
["aa", "b"]
因此你要返回的最少分割次数是 1。

相关视频：回文子串个数

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(n^2)
  public int minCutDP(String s) {
    if (s == null || s.length() == 0) return -1;
    int n = s.length();
    boolean[][] d = new boolean[n][n];
    for (int i = n-1; i >= 0; --i) {
      for (int j = i; j < n; ++j) {
        if (i == j) d[i][j] = true;
        else if (i+1 == j) d[i][j] = s.charAt(i) == s.charAt(j);
        else d[i][j] = s.charAt(i) == s.charAt(j) && d[i+1][j-1];
      }
    }

    int[] cut = new int[n+1];
    cut[0] = -1;
    for (int j = 0; j < n; ++j) {
      cut[j+1] = cut[j] + 1;
      for (int i = j-1; i >= 0; --i) {
        if (d[i][j]) {
          cut[j+1] = Math.min(cut[j+1], cut[i]+1);
        }
      }
    }
    return cut[n];
  }

  // Time: O(n^2), Space: O(n^2)
  public int minCutDPOpt(String s) {
    if (s == null || s.length() == 0) return -1;
    int n = s.length();
    boolean[][] d = new boolean[n][n];
    int[] cut = new int[n+1];
    cut[0] = -1;
    for (int j = 0; j < n; ++j) {
      d[j][j] = true;
      cut[j+1] = cut[j] + 1;
      for (int i = j-1; i >= 0; --i) {
        if (s.charAt(i) == s.charAt(j) && (i+1 == j || d[i+1][j-1])) {
          d[i][j] = true;
          cut[j+1] = Math.min(cut[j+1], cut[i]+1);
        }
      }
    }
    return cut[n];
  }

  private void expand(String s, int i, int j, int[] cut) {
    while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
      cut[j+1] = Math.min(cut[j+1], cut[i]+1);
      --i; ++j;
    }
  }

  // Time: O(n^2), Space: O(n)
  public int minCutExpand(String s) {
    if (s == null || s.length() == 0) return -1;
    int n = s.length();
    int[] cut = new int[n+1];
    for (int i = 0; i <= n; ++i) cut[i] = i - 1;

    for (int p = 0; p < n; ++p) {
      expand(s, p, p, cut);
      expand(s, p, p+1, cut);
    }
    return cut[n];
  }

}