分割回文串

题目详情请查看：https://leetcode-cn.com/leetbook/read/top-interview-questions/xaxi62/ (opens new window)

笔者采用了 暴力搜索 的方式来解决这个问题，做完还以为自己是用的 回溯法。其实回溯法属于暴力搜索方式，但回溯法通常是加入了约束，并剪掉相关的搜索，通常能得到一个比较好的结果（但不能保证不会出现最坏的结果，不过有时最坏的结果在现实是不存在的，类似这种特性的算法称为启发式算法）。

笔者的暴力搜索的思路相当于排列问题，比如 abb 中间有两个位置提供分割，每个位置有两种操作的可能性（记为 0 和 1 ），那么就可以利用递归的方式不断的在这些位置分割，最后得到所有的分割结果，然后过滤正确的回文串得到正确答案。代码如下：

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  let res = [];
  let wayStrs = [];
  let maxIndex = s.length - 2;

  function func(arr, index) {
    if (index > maxIndex) {
      let tr = trans(s, arr);
      wayStrs.push(tr);
      return;
    }
    let arr1 = JSON.parse(JSON.stringify(arr));
    let arr2 = JSON.parse(JSON.stringify(arr));
    arr1.push(0);
    arr2.push(1);
    func(arr1, index + 1);
    func(arr2, index + 1);
  }

  func([], 0);

  res = wayStrs.filter(el => {
    return el.every(ele => {
      return isPalindrome(ele);
    })
  })

  return res;
};

function isPalindrome(s) {
  if (!s) return false;
  s = s.toLowerCase();
  s = s.replace(/[^a-z0-9]/ig, '');
  let t = s.split('').reverse().join('');
  return t === s;
};

function trans(s, arr) {
  let startIndex = 0;
  let arr2 = [];
  for (let i = 0; i < arr.length; i++) {
    let el = arr[i];
    if (el === 1) {
      let str = s.substring(startIndex, i + 1);
      arr2.push(str);

      startIndex = i + 1;
    }
  }
  let last = s.substring(startIndex, s.length);
  last && arr2.push(last);
  return arr2;
}

笔者做这道题一开始就理解错了题目意思，提交代码多次都是结果不正确。通过了多个用例的观察才明白题目的意思，所以呀算法的正确性是最基础的，不然把代码都写完了才发现是错的，就白白浪费时间了。看题目的时候，有了自己的理解后，必须要有基本的验证，Leetcode 上面有的题目给的用例比较少，还需要自己构造简单的用例来验证算法的正确性，这样就能大大降低出错的概率了。

看了 LeetCode 的讨论，这个题目还有个思路是用回溯法：将所有区间长度的字符串是否是回文串，用动态规划思想事先得到，然后用回溯法搜索字符串区间，当搜索到叶节点就得到一个从根节点到叶节点组成的分割结果。笔者思考回溯法会比较担心会不会出现重复搜索，因为用回溯法这点是比较常出错的。