131.分割回文串

链接：131.分割回文串
难度：Medium
标签：字符串、动态规划、回溯
简介：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

题解 1 - typescript

• 编辑时间：2021-03-07
• 执行用时：372ms
• 内存消耗：67.8MB
• 编程语言：typescript
• 解法介绍：递归判断。

const map: Record<string, boolean> = {};
function isPalindrome(s: string) {
  if (map[s]) return map[s];
  const len = s.length;
  if (len === 1) return (map[s] = true);
  for (let i = 0; i < len / 2; i++) {
    if (s[i] !== s[len - i - 1]) {
      return (map[s] = false);
    }
  }
  return (map[s] = true);
}
function partition(s: string): string[][] {
  const ans: string[][] = [];
  const len = s.length;
  if (len === 1) return [[s]];
  for (let i = 0; i < len; i++) {
    const str = s.substring(0, i + 1);
    if (isPalindrome(str)) {
      i === len - 1
        ? ans.push([s])
        : ans.push(...partition(s.substring(i + 1)).map(arr => [str, ...arr]));
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-03-08
• 执行用时：288ms
• 内存消耗：60.4MB
• 编程语言：typescript
• 解法介绍：利用动态规划计算所有值，再利用回溯收集。

function partition(s: string): string[][] {
  const len = s.length;
  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 ans: string[][] = [];
  const arr: string[] = [];
  const dfs = (startIndex: number) => {
    if (startIndex === len) {
      ans.push([...arr]);
    } else {
      for (let i = startIndex; i < len; i++) {
        if (f[startIndex][i]) {
          const str = s.substring(startIndex, i + 1);
          arr.push(str);
          dfs(i + 1);
          arr.pop();
        }
      }
    }
  };
  dfs(0);
  return ans;
}