# 131. Palindrome Partitioning

/**
 * [partition description]
 * @param  {[type]} s [传入的字符串]
 * @return {[type]}   [返回所有可能的回文结构子字符串划分数组]
 */
let partition = function(s) {
  let result = [];
  let partition = [];
  if (s === null || s.length === 0) return result;

  addPalindrome(s, 0, partition, result);
  return result;
};
function addPalindrome(s, start, partition, result) {
  if (start === s.length) {
    //因为partition会不断改变，所以temp只保存符合条件的数组值，
    //如果直接=是js引用,temp会根据partition的变化而变化，
    //因此要以js赋值的写法写
    let temp = [].concat(partition);
    result.push(temp);
    return;
  }
  for (let i = start + 1; i <= s.length; i++) {
    //循环截取字符串
    let str = s.substring(start, i);
    //判断是否是回文，如果是，存入临时数组partition中，递归调用addPalindrome函数，将符合条件的数组添加给result
    if (isPalindrome(str)) {
      partition.push(str);
      //当i<=3 的时候递归调用addPalindrome
      //1:1,2,3
      //2:2,3
      //3=3直接跳过
      addPalindrome(s, i, partition, result);
      partition.splice(partition.length - 1, 1);
    }
  }
}
//判断字符串是否是回文
function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    if (str.charAt(left) != str.charAt(right)) {
      return false;
    }
    left++;
    right--;
  }
  return true;
}