LeetCode算法編程 - Palindrome Partitioning
1、題目
復制代碼
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<string> &sln,
vector<vector<string> > &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<vector<string> > partition(string s) {
vector<string> sln;
vector<vector<string> > result;
find_partition_sln(s, sln, result);
return result;
}
};
