题目

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

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

题解

我们这里声明两个函数，分别是isPalindrome 和 partition函数。 isPalindrome 的功能是判断一个字符串是否是回文的。该函数首先将传入的字符串 s 分割成单个字符的数组 token，然后利用双指针方法，分别指向第一个和最后一个字符，同时从两端遍历比较字符是否一致。如果两个字符不同，则说明该字符串不是回文的，返回 false，如果两个字符相同，则继续往中间靠拢。当左指针大于等于右指针时，说明该字符串是回文的，返回 true。函数 partition 的功能是将一个字符串 s 拆分成回文子串的所有可能组合。该函数首先定义了一个空数组 ans，后面用于存储所有可能的回文组合情况。然后定义了一个递归函数 subStr，用于在字符串中从前往后依次尝试组合每一个回文子串。函数 subStr 接收三个参数，分别是当前遍历到的字符在字符串中的下标 index、当前组合的字符串 str、已组合好的子串数组 arr。函数 subStr 的主体是一个循环体，该循环体的作用是对下一个字符进行判断和组合。首先尝试将下一个字符添加到当前组合字符串 str 后面，继续递归调用 subStr。然后判断当前组合字符串是否是回文的，如果不是回文的，则直接返回。如果是回文的，则将当前组合字符串 str 添加到已组合好的子串数组 arr 中，再递归调用 subStr 继续向后组合，同时将已组合好的子串数组 arr 作为参数传入下一个递归调用。当所有字符都遍历完成后，将已组合好的子串数组 arr 添加到结果集数组 ans 中。最后，函数 partition 在调用递归函数 subStr 时，传入当前遍历到的第一个字符和一个空的已组合好的子串数组 []。当递归函数 subStr 执行完成后，函数 partition 将结果集 ans 返回

 var isPalindrome = function(s) {
      let token = s.split("");
      if(token.length === 0) return true;
      let i = 0,j = token.length-1;
      while(j>i){
          if(token[i] === token[j]){
              i++;j--;
          }else{
              return false;
          }
      }
      return true;
  };
  var partition = function(s) {
      let len = s.length;
      let ans = [];
      function subStr(index,str,arr){
          if(index>=len){
              ans.push(arr.slice());
              return;
          }
          if(index+1<len) subStr(index+1,str+s[index+1],arr);
          if(!isPalindrome(str)) return;
          arr.push(str);
          subStr(index+1,s[index+1],arr);
          arr.pop();
      }
      subStr(0,s[0],[]);
      return ans;
  }