132.分割回文串II

链接：132.分割回文串II
难度：Hard
标签：字符串、动态规划
简介：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的 最少分割次数 。

题解 1 - typescript

• 编辑时间：2021-03-08
• 执行用时：160ms
• 内存消耗：57.68MB
• 编程语言：typescript
• 解法介绍：动态规划。

function minCut(s: string): number {
  const len = s.length;
  if (len <= 1) return 0;
  const f = new Array(len).fill(0).map(() => new Array(len).fill(true));
  for (let i = len - 1; i >= 0; --i) {
    for (let j = i + 1; j < len; ++j) {
      f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
    }
  }
  const dp: number[] = new Array(len).fill(Infinity);
  for (let i = 0; i < len; i++) {
    if (f[0][i]) {
      dp[i] = 0;
    } else {
      for (let j = 0; j < i; j++) {
        if (f[j + 1][i]) {
          dp[i] = Math.min(dp[i], dp[j] + 1);
        }
      }
    }
  }
  return dp[len - 1];
}

题解 2 - typescript

• 编辑时间：2021-12-12
• 执行用时：220ms
• 内存消耗：76.6MB
• 编程语言：typescript
• 解法介绍：先统计所有的以 i 开头 j 结尾的回文字符串，进行动态规划遍历。

function getArr(s: string) {
  const n = s.length;
  const ans = new Array(n).fill(0).map(_ => new Array(n).fill(false));
  const load = (l: number, r: number) => {
    while (l >= 0 && r < n && s[l] === s[r]) ans[l--][r++] = true;
  };
  for (let i = 0; i < n; i++) {
    load(i, i);
    if (i < n - 1) load(i, i + 1);
  }
  return ans;
}
function minCut(s: string): number {
  const n = s.length;
  const arr = getArr(s);
  const dp = new Array(n).fill(0).map((_, i) => i);
  for (let i = 0; i < n; i++) {
    if (arr[0][i]) {
      dp[i] = 0;
      continue;
    }
    for (let j = 0; j + 1 <= i; j++) {
      if (!arr[j + 1][i]) continue;
      dp[i] = Math.min(dp[i], dp[j] + 1);
    }
  }
  return dp[n - 1];
}