原文：131. 分割回文串(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0131/

题目：

难度：Middle

相关话题：回溯算法

给定一个字符串 s ，将s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入:"aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

思路：

回溯，start为从当前哪个索引开始，检测以start为开头的每一个子字符串，如果存在回文字符串，就添加到arr中，直到start===s.length， 说明当前arr为其中一个解，添加到结果result中。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  let result=[]
  backtrack([],0)
  return result

  function isP(str){
    for(let i=0;i<str.length/2;i++){
      if(str[i]!==str[str.length-1-i])return false
    }
    return true
  }
  function backtrack(arr,start){
    if(start===s.length) result.push(arr.slice())
    for(let i=start;i<s.length;i++){
      let str=s.substring(start,i+1)
      if(isP(str)){
        arr.push(str)
        backtrack(arr,i+1)
        arr.pop()
      }
    }
  }
};

扩展阅读：