分割回文串 II

[louzhedong]

习题

出处 LeetCode 算法第132题

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

思路

采用DFS的方式能得出结果，但是会出现超时的情况，所以采用动态规划的方式

解答

var minCut = function (s) {
  var length = s.length;
  var dp = [];
  for (var i = 0; i < length; i++) {
    dp[i] = [];
    for (var j = 0; j < length; j++) {
      dp[i][j] = false;
    }
  }
  var minArray = [];
  var min;
  for (var i = 0; i < length; i++) {
    min = i;
    for (var j = 0; j <= i; j++) {
      if (s[i] == s[j] && (j + 1 > i - 1 || dp[j + 1][i - 1])) {
        dp[j][i] = true;
        if (j == 0) min = 0;
        else {
          min = Math.min(min, minArray[j - 1] + 1);
        }
      }
    }
    minArray[i] = min;
  }
  return minArray[length - 1];
};