1
var minCut = function (s) {
2
  function isPal(l, r) {
3
    while (l < r) {
4
      if (s[l] === s[r]) l++, r--;
5
      else return false;
6
    }
7
    return true;
8
  }
9

10
  let map = new Map();
11
  function dfs(idx = 0) {
12
    if (idx === s.length) return 0;
13
    if (map.has(idx)) return map.get(idx);
14
    let min = Infinity;
15
    for (let i = idx; i < s.length; i++) {
16
      if (isPal(idx, i)) min = Math.min(min, 1 + dfs(i + 1));
17
    }
18
    map.set(idx, min);
19
    return min;
20
  }
21

22
  return dfs() - 1;
23
};