分割回文串-中等

难度：中等

题目描述：
给定一个字符串 s，将* s *分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

示例：

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

1
2
3
4
5

解题思路：

var partition = function (s) {
  let ans = [];
  const backTrack = function (start, path) {
    //当起点和s字符串一样长的时候，说明已经无剩余字符串可以裁剪了，停止，保存路径
    if (start == s.length) {
      ans.push(path);
      return;
    }
    for (let i = start; i < s.length; i++) {
      let strs = s.slice(start, i + 1);
      if (strs && isOK(strs)) {
        //起始改为i+1，保存路径节点path.concat(strs)
        backTrack(i + 1, path.concat(strs));
      }
    }
  };
  backTrack(0, []);
  return ans;
};
//判断是否回文,该方法效率较低，仅为了书写方便
function isOK(str) {
  return str.split("").reverse().join("") === str;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

← 电话号码的字母组合-中等括号生成-中等 →

# 分割回文串-中等

分割回文串-中等