Appearance
132. 分割回文串 II
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
**输入：**s = "aab" **输出：**1 **解释：**只需一次分割就可将 *s *分割成 ["aa","b"] 这样两个回文子串。
示例 2：
**输入：**s = "a" **输出：**0
示例 3：
**输入：**s = "ab" **输出：**1
提示：
- `1 <= s.length <= 2000`
- `s` 仅由小写英文字母组成
难度： Hard
题解代码
javascript
/**
* @param {string} s
* @return {number}
*/
// let min = Infinity
// var minCut = function(s) {
// min = Infinity
// backtrack(s, [])
// return min
// };
// function backtrack (s, path) {
// if (!s.length) {
// min = Math.min(min, path.length - 1)
// return
// }
// for(let i = 1; i < s.length + 1; i++) {
// const item = s.slice(0, i)
// if (!isValid(item)) continue
// path.push(item)
// s = s.slice(i)
// backtrack(s, path)
// s = path.pop() + s
// }
// }
// function isValid (s) {
// let start = 0, end = s.length - 1
// for (i = start, j = end; i < j; i++, j--) {
// if (s[i] !== s[j]) return false
// }
// return true
// }
var minCut = function(s) {
let min = Infinity
const dfs = (i) => {
if (i === n) {
// ret.push(ans.slice());
min = Math.min(min, ans.length - 1)
return;
}
for (let j = i; j < n; ++j) {
if (f[i][j]) {
ans.push(s.slice(i, j + 1));
dfs(j + 1);
ans.pop();
}
}
}
const n = s.length;
const f = new Array(n).fill(0).map(() => new Array(n).fill(true));
let ans = [];
for (let i = n - 1; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
f[i][j] = (s[i] === s[j]) && f[i + 1][j - 1];
}
}
dfs(0);
return min;
};