131. 分割回文串

题目

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

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

题解

回溯

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  let res = [];
  let path = [];

  // 回溯 index 字符串起始位置
  function backtracking(s, index) {
    // 位置超过字符串长度，加入结果
    if (index >= s.length) {
      res.push([...path]);
      return;
    }

    for (let i = index; i < s.length; ++i) {
      // 判断所有 index 起始的子字符串是否是回文
      if (isPalindrome(s, index, i)) {
        // 是就加入
        let str = s.substr(index, i - index + 1);
        path.push(str);
      } else continue;
      // 回溯接着的子字符串
      backtracking(s, i + 1);
      path.pop();
    }
  }

  // 判断是否是回文
  function isPalindrome(s, begin, end) {
    for (let i = begin, j = end; i < j; i++, j--) {
      if (s[i] != s[j]) return false;
    }
    return true;
  }

  backtracking(s, 0);
  return res;
};