leetcode-131-分割回文串

我正在参加「掘金·启航计划」
题目地址

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

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

示例 1：

输入： s = "aab"
输出： [["a","a","b"],["aa","b"]]

示例 2：

输入： s = "a"
输出： [["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

解题思路-基础

本题最简单的思路就是按照题意一步步处理即可。所以我们首先需要一个方案去校验当前拿到的子串是否是回文串，也就是下面的 check。然后为了不做重复的校验，我们还需要一个 map 记录已经校验过的结果，也就是下面的 checkedRecord。接下来就是扫描字符串，然后基于当前的子串是否是回文串以及当前是否已处理完输入字符串进行不同的逻辑处理。

代码实现

const checkedRecord = new Map()
function check(str) {
  let l = 0
  let r = str.length - 1
  while (l < r) {
    if (str[l] !== str[r]) {
      checkedRecord.set(str, false)
      return false
    }
    l++
    r--
  }
  checkedRecord.set(str, true)
  return true
}
function cut(str, pre, index, end, item, res) {
  if (index > end) {
    return
  }
  pre += str[index]
  const isPrePalindrome = checkedRecord.get(pre) || check(pre)

  // 如果当前是最后一个字符
  if (index === end) {
    // 且pre是回文串，说明找到了一组新的方案
    isPrePalindrome && res.push([...item, pre])
  } else {
    // 下标+1，尝试找出另一种方案
    cut(str, pre, index + 1, end, [...item], res)
    // 如果pre是回文串，将pre存入item,继续向后处理
    if (isPrePalindrome) {
      cut(str, '', index + 1, end, [...item, pre], res)
    }
  }
}
var partition = function (s) {
  const res = []

  cut(s, '', 0, s.length - 1, [], res)

  return res
};

解题思路-进阶

上面的思路肯定是能解出本题的，但是有那么一点憨 😅
接来下我们借助动态规划让它略显高端一点 😝
其实本题最耗时的地方明显就是每次校验当前子串是否是回文串这个操作，这一步其实我们可以通过动归快速的求解所有子串是否是回文串，然后在查找组合方案的时候只需要取结果中获取下当前子串是否是回文串即可。
首先是状态定义，这里我们定义二维dp dp[i][j]，代表下标 i~j的字符串是否是回文串；
接下来是状态转移方程，如果 i===j，那么肯定是回文串；
如果 i+1 === j && s[i] === s[j]，那么肯定是回文串；
如果 j-i>1 && dp[i+1][j-1]，那么肯定是回文串；
如果 j-i>1 && !dp[i][j]，那么肯定不是回文串。
有了这样一个二维dp，接下来寻找所有可能的组合方案时就变得又快又高端了不是 😏

代码实现

// 寻找所有可能的方案
function dfs(s, dp, item, start, end, res) {
  if (start == end) {
    res.push([...item])
    return
  }
  for (let j = start; j < end; j++) {
    if (dp[start][j]) {
      dfs(s, dp, [...item, s.substring(start, j + 1)], j + 1, end, res)
    }
  }
}
var partition = function (s) {
  // 记录输入字符串长度
  const len = s.length
  // 初始化结果数组
  const res = []
  // 初始化 二维dp
  const dp = new Array(len).fill(0).map(() => new Array(len).fill(true))
  // 求得所有dp值
  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      dp[i][j] = i === j ? true : (s[i] === s[j]) && dp[i + 1][j - 1]
    }
  }

  dfs(s, dp, [], 0, len, res)

  return res
};

至此我们就完成了 leetcode-131-分割回文串

如有任何问题或建议，欢迎留言讨论！