分割回文串，有點難！
切割問題其實是一種組合問題!
分割回文串
力扣題目鏈接：https://leetcode-cn.com/problems/palindrome-partitioning/
給定一個字符串 s，將 s 分割成一些子串，使每個子串都是回文串。
返回 s 所有可能的分割方案。
示例:
輸入: "aab"
輸出: [ ["aa","b"], ["a","a","b"] ]
思路
本題這涉及到兩個關鍵問題：
- 切割問題，有不同的切割方式
- 判斷回文
相信這里不同的切割方式可以搞懵很多同學了。
這種題目，想用for循環暴力解法，可能都不那么容易寫出來，所以要換一種暴力的方式，就是回溯。
一些同學可能想不清楚 回溯究竟是如何切割字符串呢?
我們來分析一下切割，其實切割問題類似組合問題。
例如對于字符串abcdef：
- 組合問題：選取一個a之后，在bcdef中再去選取第二個，選取b之后在cdef中在選組第三個.....。
- 切割問題：切割一個a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。
感受出來了不?
所以切割問題，也可以抽象為一顆樹形結構，如圖：
分割回文串
遞歸用來縱向遍歷，for循環用來橫向遍歷，切割線(就是圖中的紅線)切割到字符串的結尾位置，說明找到了一個切割方法。
此時可以發現，切割問題的回溯搜索的過程和組合問題的回溯搜索的過程是差不多的。
回溯三部曲
- 遞歸函數參數
全局變量數組path存放切割后回文的子串，二維數組result存放結果集。(這兩個參數可以放到函數參數里)
本題遞歸函數參數還需要startIndex，因為切割過的地方，不能重復切割，和組合問題也是保持一致的。
在39. 組合總和中我們深入探討了組合問題什么時候需要startIndex，什么時候不需要startIndex。
代碼如下：
- vector<vector<string>> result;
- vector<string> path; // 放已經回文的子串
- void backtracking (const string& s, int startIndex) {
- 遞歸函數終止條件
分割回文串
從樹形結構的圖中可以看出：切割線切到了字符串最后面，說明找到了一種切割方法，此時就是本層遞歸的終止終止條件。
那么在代碼里什么是切割線呢?
在處理組合問題的時候，遞歸參數需要傳入startIndex，表示下一輪遞歸遍歷的起始位置，這個startIndex就是切割線。
所以終止條件代碼如下：
- void backtracking (const string& s, int startIndex) {
- // 如果起始位置已經大于s的大小，說明已經找到了一組分割方案了
- if (startIndex >= s.size()) {
- result.push_back(path);
- return;
- }
- }
- 單層搜索的邏輯
來看看在遞歸循環，中如何截取子串呢?
在for (int i = startIndex; i < s.size(); i++)循環中，我們 定義了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判斷這個子串是不是回文，如果是回文，就加入在vector
代碼如下：
- for (int i = startIndex; i < s.size(); i++) {
- if (isPalindrome(s, startIndex, i)) { // 是回文子串
- // 獲取[startIndex,i]在s中的子串
- string str = s.substr(startIndex, i - startIndex + 1);
- path.push_back(str);
- } else { // 如果不是則直接跳過
- continue;
- }
- backtracking(s, i + 1); // 尋找i+1為起始位置的子串
- path.pop_back(); // 回溯過程，彈出本次已經填在的子串
- }
注意切割過的位置，不能重復切割，所以，backtracking(s, i + 1); 傳入下一層的起始位置為i + 1。
判斷回文子串
最后我們看一下回文子串要如何判斷了，判斷一個字符串是否是回文。
可以使用雙指針法，一個指針從前向后，一個指針從后先前，如果前后指針所指向的元素是相等的，就是回文字符串了。
那么判斷回文的C++代碼如下：
- bool isPalindrome(const string& s, int start, int end) {
- for (int i = start, j = end; i < j; i++, j--) {
- if (s[i] != s[j]) {
- return false;
- }
- }
- return true;
- }
如果大家對雙指針法有生疏了，傳送門：雙指針法：總結篇!
此時關鍵代碼已經講解完畢，整體代碼如下(詳細注釋了)
C++整體代碼
根據Carl給出的回溯算法模板：
- void backtracking(參數) {
- if (終止條件) {
- 存放結果;
- return;
- }
- for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
- 處理節點;
- backtracking(路徑，選擇列表); // 遞歸
- 回溯，撤銷處理結果
- }
- }
不難寫出如下代碼：
- class Solution {
- private:
- vector<vector<string>> result;
- vector<string> path; // 放已經回文的子串
- void backtracking (const string& s, int startIndex) {
- // 如果起始位置已經大于s的大小，說明已經找到了一組分割方案了
- if (startIndex >= s.size()) {
- result.push_back(path);
- return;
- }
- for (int i = startIndex; i < s.size(); i++) {
- if (isPalindrome(s, startIndex, i)) { // 是回文子串
- // 獲取[startIndex,i]在s中的子串
- string str = s.substr(startIndex, i - startIndex + 1);
- path.push_back(str);
- } else { // 不是回文，跳過
- continue;
- }
- backtracking(s, i + 1); // 尋找i+1為起始位置的子串
- path.pop_back(); // 回溯過程，彈出本次已經填在的子串
- }
- }
- bool isPalindrome(const string& s, int start, int end) {
- for (int i = start, j = end; i < j; i++, j--) {
- if (s[i] != s[j]) {
- return false;
- }
- }
- return true;
- }
- public:
- vector<vector<string>> partition(string s) {
- result.clear();
- path.clear();
- backtracking(s, 0);
- return result;
- }
- };
總結
這道題目在leetcode上是中等，但可以說是hard的題目了，但是代碼其實就是按照模板的樣子來的。
那么難究竟難在什么地方呢?
我列出如下幾個難點：
- 切割問題可以抽象為組合問題
- 如何模擬那些切割線
- 切割問題中遞歸如何終止
- 在遞歸循環中如何截取子串
- 如何判斷回文
我們平時在做難題的時候，總結出來難究竟難在哪里也是一種需要鍛煉的能力。
一些同學可能遇到題目比較難，但是不知道題目難在哪里，反正就是很難。其實這樣還是思維不夠清晰，這種總結的能力需要多接觸多鍛煉。
本題我相信很多同學主要卡在了第一個難點上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是沒有體會到按照求組合問題的套路就可以解決切割。
如果意識到這一點，算是重大突破了。接下來就可以對著模板照葫蘆畫瓢。
但接下來如何模擬切割線，如何終止，如何截取子串，其實都不好想，最后判斷回文算是最簡單的了。
關于模擬切割線，其實就是index是上一層已經確定了的分割線，i是這一層試圖尋找的新分割線
除了這些難點，本題還有細節，例如：切割過的地方不能重復切割所以遞歸函數需要傳入i + 1。
所以本題應該是一個道hard題目了。
可能刷過這道題目的錄友都沒感受到自己原來克服了這么多難點，就把這道題目AC了，這應該叫做無招勝有招，人碼合一，哈哈哈。
本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。
