131-分割回文串.md

题目描述

分割回文串

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

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

示例 1：

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

分类

中等 字符串 回溯

思路

思路1

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  const res = []
  const tempRes = []
  const backTrack = function (index) {
    // index === s.length
    if (index === s.length) {
      res.push([...tempRes])
      return
    }
    let str = ''
    for (let i = index; i < s.length; i ++) {
      str += s[i]
      if (verifyStr(str)) {
        tempRes.push(str)
        backTrack(i + 1)
        tempRes.pop()
      }
    }
  }
  backTrack(0)
  return res
};  
const verifyStr = function (s) {
  if (!s) {
    return false
  }
  let res = true
  for (let charIndex = 0; charIndex < Math.round(s.length / 2); charIndex ++) {
    if (s[charIndex] !== s[s.length - charIndex - 1]) {
      res = false
      break
    }
  }
  return res
}

• 问题分析
  • 将字符串拆分为多个字串，且每个字串都是回文串。所以我们通过回溯来解决思路是：
    • 回溯函数backTrack作用：分割字符串为两段，如果前一段为回文串，则将后一段交给下一个backTrack处理。这里的后一段，并非传入的是字符串，而是相对于字符串的位置index。
    • 如何进行切割：每个字符依次进行分割，从第一、二个字符开始，直到最后一位。
    • 回溯终止条件：第一次分割时，分割的位置是整个字符串的末尾index === s.length
    • 回溯可能性查找：从index开始的字符，到字符串末尾。
  • 回文串判断
    • 对字符串进行遍历，判断第i位和s.length - 1 - i位是否相同。