[[426079]]

切割問題其實(shí)是一種組合問題!

分割回文串

力扣題目鏈接：https://leetcode-cn.com/problems/palindrome-partitioning/

給定一個字符串 s，將 s 分割成一些子串，使每個子串都是回文串。

返回 s 所有可能的分割方案。

示例:

輸入: "aab"

輸出: [ ["aa","b"], ["a","a","b"] ]

思路

本題這涉及到兩個關(guān)鍵問題：

1. 切割問題，有不同的切割方式
2. 判斷回文

相信這里不同的切割方式可以搞懵很多同學(xué)了。

這種題目，想用for循環(huán)暴力解法，可能都不那么容易寫出來，所以要換一種暴力的方式，就是回溯。

一些同學(xué)可能想不清楚 回溯究竟是如何切割字符串呢?

我們來分析一下切割，其實(shí)切割問題類似組合問題。

例如對于字符串a(chǎn)bcdef：

• 組合問題：選取一個a之后，在bcdef中再去選取第二個，選取b之后在cdef中在選組第三個.....。
• 切割問題：切割一個a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。

感受出來了不?

所以切割問題，也可以抽象為一顆樹形結(jié)構(gòu)，如圖：

分割回文串

遞歸用來縱向遍歷，for循環(huán)用來橫向遍歷，切割線(就是圖中的紅線)切割到字符串的結(jié)尾位置，說明找到了一個切割方法。

此時可以發(fā)現(xiàn)，切割問題的回溯搜索的過程和組合問題的回溯搜索的過程是差不多的。

回溯三部曲

• 遞歸函數(shù)參數(shù)

全局變量數(shù)組path存放切割后回文的子串，二維數(shù)組result存放結(jié)果集。(這兩個參數(shù)可以放到函數(shù)參數(shù)里)

本題遞歸函數(shù)參數(shù)還需要startIndex，因?yàn)榍懈钸^的地方，不能重復(fù)切割，和組合問題也是保持一致的。

在39. 組合總和中我們深入探討了組合問題什么時候需要startIndex，什么時候不需要startIndex。

代碼如下：

vector<vector<string>> result; 
vector<string> path; // 放已經(jīng)回文的子串 
void backtracking (const string& s, int startIndex) { 

• 遞歸函數(shù)終止條件

分割回文串

從樹形結(jié)構(gòu)的圖中可以看出：切割線切到了字符串最后面，說明找到了一種切割方法，此時就是本層遞歸的終止終止條件。

那么在代碼里什么是切割線呢?

在處理組合問題的時候，遞歸參數(shù)需要傳入startIndex，表示下一輪遞歸遍歷的起始位置，這個startIndex就是切割線。

所以終止條件代碼如下：

void backtracking (const string& s, int startIndex) { 
    // 如果起始位置已經(jīng)大于s的大小，說明已經(jīng)找到了一組分割方案了 
    if (startIndex >= s.size()) { 
        result.push_back(path); 
        return; 
    } 
} 

• 單層搜索的邏輯

來看看在遞歸循環(huán)，中如何截取子串呢?

在for (int i = startIndex; i < s.size(); i++)循環(huán)中，我們 定義了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判斷這個子串是不是回文，如果是回文，就加入在vector path中，path用來記錄切割過的回文子串。

代碼如下：

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();        // 回溯過程，彈出本次已經(jīng)填在的子串 
} 

注意切割過的位置，不能重復(fù)切割，所以，backtracking(s, i + 1); 傳入下一層的起始位置為i + 1。

判斷回文子串

最后我們看一下回文子串要如何判斷了，判斷一個字符串是否是回文。

可以使用雙指針法，一個指針從前向后，一個指針從后先前，如果前后指針?biāo)赶虻脑厥窍嗟鹊?，就是回文字符串了?/p>

那么判斷回文的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; 
} 

如果大家對雙指針法有生疏了，傳送門：雙指針法：總結(jié)篇!

此時關(guān)鍵代碼已經(jīng)講解完畢，整體代碼如下(詳細(xì)注釋了)

C++整體代碼

根據(jù)Carl給出的回溯算法模板：

void backtracking(參數(shù)) { 
    if (終止條件) { 
        存放結(jié)果; 
        return; 
    } 
 
    for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) { 
        處理節(jié)點(diǎn); 
        backtracking(路徑，選擇列表); // 遞歸 
        回溯，撤銷處理結(jié)果 
    } 
} 

不難寫出如下代碼：

class Solution { 
private: 
    vector<vector<string>> result; 
    vector<string> path; // 放已經(jīng)回文的子串 
    void backtracking (const string& s, int startIndex) { 
        // 如果起始位置已經(jīng)大于s的大小，說明已經(jīng)找到了一組分割方案了 
        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(); // 回溯過程，彈出本次已經(jīng)填在的子串 
        } 
    } 
    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; 
    } 
}; 

總結(jié)

這道題目在leetcode上是中等，但可以說是hard的題目了，但是代碼其實(shí)就是按照模板的樣子來的。

那么難究竟難在什么地方呢?

我列出如下幾個難點(diǎn)：

• 切割問題可以抽象為組合問題
• 如何模擬那些切割線
• 切割問題中遞歸如何終止
• 在遞歸循環(huán)中如何截取子串
• 如何判斷回文

我們平時在做難題的時候，總結(jié)出來難究竟難在哪里也是一種需要鍛煉的能力。

一些同學(xué)可能遇到題目比較難，但是不知道題目難在哪里，反正就是很難。其實(shí)這樣還是思維不夠清晰，這種總結(jié)的能力需要多接觸多鍛煉。

本題我相信很多同學(xué)主要卡在了第一個難點(diǎn)上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是沒有體會到按照求組合問題的套路就可以解決切割。

如果意識到這一點(diǎn)，算是重大突破了。接下來就可以對著模板照葫蘆畫瓢。

但接下來如何模擬切割線，如何終止，如何截取子串，其實(shí)都不好想，最后判斷回文算是最簡單的了。

關(guān)于模擬切割線，其實(shí)就是index是上一層已經(jīng)確定了的分割線，i是這一層試圖尋找的新分割線

除了這些難點(diǎn)，本題還有細(xì)節(jié)，例如：切割過的地方不能重復(fù)切割所以遞歸函數(shù)需要傳入i + 1。

所以本題應(yīng)該是一個道hard題目了。

可能刷過這道題目的錄友都沒感受到自己原來克服了這么多難點(diǎn)，就把這道題目AC了，這應(yīng)該叫做無招勝有招，人碼合一，哈哈哈。

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。