131. Palindrome Partitioning

1function partition(s: string): string[][] {
2  const n = s.length, pal = Array.from({ length: n }, () => new Array(n).fill(false));
3  for (let i = n - 1; i >= 0; i--)
4    for (let j = i; j < n; j++)
5      pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);
6  const res: string[][] = [], path: string[] = [];
7  function dfs(start: number) {
8    if (start === n) { res.push([...path]); return; }
9    for (let end = start; end < n; end++)
10      if (pal[start][end]) {
11        path.push(s.slice(start, end + 1)); dfs(end + 1); path.pop();
12      }
13  }
14  dfs(0);
15  return res;
16}

pal[3][3] ("b") = true.

Space: play/pause · ←/→: step