分割回文串

Question

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

回文串 是正着读和反着读都一样的字符串。

思路

**关键思想：**切割问题类似组合问题

切割哪个区间可以转化为选取哪个元素作为当前区间的最后一个元素，比如说aab，先选a意思就是在a后面画一道分割线

确定参数和返回值：全局变量path和res
- path：路径就表示了一种切割方案
- res：存储所有符合条件的切割方案
- startIndex：表示下一次切割的起始位置，本题中也表示切割线的位置
终止条件的确定：切到头了，切割线位于最后一个元素（叶子结点）
单层逻辑：判断是否回文，str[sratIndex,i]就是单层搜索里面的那个子串，也是我们判断的对象
回文的判断：双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。

var partition = function(s) {
    const path = []
    const res = []
    const backtracking = (startIndex)=>{
        if( startIndex>=s.length){					//终止条件
            res.push([...path])		
            return
        }
        for(let i=startIndex; i< s.length; i++){	// 本层集合中元素
            let str = s.slice(startIndex,i+1)
            if(isPalindrome(str))
                path.push(str)
            else
                continue		
            backtracking(i+1)						//树枝去重
            path.pop()		
        }
    }
    backtracking(0)
    return res
};

//判断是否回文
var isPalindrome = function(s) {
    let left = 0
    let right = s.length-1
    while(left<right){
        if(s[left++]!=s[right--])
            return false
    }
    return true
}

分割回文串 ​

思路 ​

分割回文串

思路