Problem
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: “aab”
Output:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]
Solution
解析
回溯法。解决方法和求字符串排列结果类似。这里因为是回文串,每次从0开始,回文串长度从1变化到str.size();尝试一次划分,如果划分结果是回文串,插入到划分结果中,如果不是,尝试下一个长度。终止条件是index指向字符串末尾’\0’. 值得注意的是,回溯法,最好调用递归之后,进行回溯,返回到原来的状态,否则,容易出错(没错就是你!)。
解法
1 | class Solution { |