?
复制代码
Given a string s, partition s such that every substring of the partition is a palindrome.
?
Return all possible palindrome partitioning of s.
?
For example, given s = "aab",
Return
?
? [
? ? ["aa","b"],
? ? ["a","a","b"]
? ]
复制代码
题目解释：
?
指定字符串 s，返回 s 所有可能的子串，每个子串必须是一个回文（指顺读和倒读都一样的字符串），示例如上图。
?
?
?
分析
?
仔细思考一下问题，会发现题目的做法是遍历所有的可能，找出合适的解。大家可以先尝试下自已写这个算法，这道题会考验递归的基本功。
?
?
?
先介绍下回溯算法，回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：
?
1、定义一个解空间，它包含问题的解。
?
2、利用适于搜索的方法组织解空间。
?
3、利用深度优先法搜索解空间。
?
4、利用限界函数避免移动到不可能产生解的子空间。
?
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
?
?
?
源码：
?
复制代码
class Solution {
public:
?
? ? // 检查一个字符串是否为回文
? ? bool check_palindrome(string s)
? ? {
? ? ? ? int size = s.size();
? ? ? ? for (int i = 0; i < size/2; i ++)
? ? ? ? {
? ? ? ? ? ? if (s[i] != s[size - i - 1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? return true;
? ? }
?
? ? void find_partition_sln(string s,?
? ? ? ? ? ? ? ? ? ? ? ? ? ? vector &sln,?
? ? ? ? ? ? ? ? ? ? ? ? ? ? vector > &result)
? ? {
? ? ? ? // 边界结束条件
? ? ? ? if (s.size() == 0)
? ? ? ? {
? ? ? ? ? ? // 能到这，说明找到了一个可能的解，前面的子串都是符合条件的
? ? ? ? ? ? result.push_back(sln);
? ? ? ? }
?
? ? ? ? int size = s.size();
?
? ? ? ? // 把字符串从第一个位置到最后一个位置，依次进行分隔
? ? ? ? // 并在每一种情况下，利用深度搜索找到合适的解
? ? ? ? for (int i = 1; i <= size; i ++)
? ? ? ? {
? ? ? ? ? ? string front;
? ? ? ? ? ? string remain;
?
? ? ? ? ? ? front.assign(s, 0, i);
? ? ? ? ? ? remain.assign(s, i, size - i);
?
? ? ? ? ? ? if (check_palindrome(front))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? // front符合条件
? ? ? ? ? ? ? ? sln.push_back(front);
?
? ? ? ? ? ? ? ? // 寻找以front开头的可行解，深度优先
? ? ? ? ? ? ? ? find_partition_sln(remain, sln, result);
?
? ? ? ? ? ? ? ? // 重新开始下一个查找
? ? ? ? ? ? ? ? sln.pop_back();
? ? ? ? ? ? }
? ? ? ? }
? ? }
?
? ? vector > partition(string s) {
?
? ? ? ? vector sln;
? ? ? ? vector > result;
? ? ? ??
? ? ? ? find_partition_sln(s, sln, result);
?
? ? ? ? return result;
? ? }
};