【LeetCode精选TOP面试题】131-分隔回文串

LeetCode 原题链接

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

动态规划+回溯

思路

从左到右遍历字符串，如果左串是回文串则递归拆分右串，如果能将字符串完整扫描一遍说明这次的扫描路径是一种合法的分割方案。

通过动态规划求得字符串的所有子回文串信息，用于在回溯中判断子串是否为回文串。

字符串 aba 的回溯树如下：

aba {
  a {     // aba从第一位分割，左串为a，右串为ab，左串为回文串则继续拆分ba
    b {     // ba从第一位分割，左串为b，右串为a，左串为回文串则继续拆分a
      a {
              // a从第一位分割，左串为a，右串为空，左串为回文串则继续拆分空串，下次递归时发现字符串已扫描完毕，说明这次的拆分路径是一种合法的分割方案
      }
    }

    ba      // ba从第二位分割，左串为ba，左串不是回文串，结束拆分
  }

  ab      // aba从第二位分割，左串为ab，右串为a，左串不是回文串，结束拆分

  aba     // aba从第三位分割，左串为aba，右串为空，左串为回文串，下次递归时发现字符串已扫描完毕，说明这次的拆分路径是一种合法的分割方案
}

复杂度

• 时间复杂度：O(n*2^n)，n 是字符串的长度，最坏情况下，s 包含 n 个完全相同的字符，此时它的划分方案数为 2^(n-1) = O(2^n)，每种划分方案需要 O(n) 的事件求出对应的划分结果（递归）并放入答案，因此总时间复杂度为 O(n*2^n)，动态规划预处理的时间复杂度为 O(n^2)。

• 空间复杂度：O(n^2)，此空间为保存动态规划结果所需的空间，在回溯法中需要 O(n) 的空间来存储当前字符串分割方法的空间，还需要 O(n) 的空间存储递归的函数调用栈。

代码

var partition = function (s) {
  // 动态规划获取子回文串信息
  const n = s.length;
  const f = new Array(n).fill(0).map(() => new Array(n).fill(true));

  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];
    }
  }

  // 回溯法查找所有合法的分割方案
  let ret = [],
    ans = [];
  const dfs = (i) => {
    if (i === n) {
      ret.push(ans.slice()); // 已经遍历到最后了，保存当前路径
      return;
    }
    for (let j = i; j < n; ++j) {
      if (f[i][j]) {
        // 左串是回文串
        ans.push(s.slice(i, j + 1)); // 往当前路径中添加左串
        dfs(j + 1);
        ans.pop(); // ans保存的是当前的拆分路径，每一次子递归都会向里面添加数据，在递归完成后pop掉最后一次添加的数据，这样可以保证在下次递归时ans是干净的
      }
    }
  };
  dfs(0);
  return ret;
};

let result = partition("aabaa");
console.log(result);