[[426079]]

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

分割回文串

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

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

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

示例:

輸入: "aab"

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

思路

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

1. 切割問(wèn)題，有不同的切割方式
2. 判斷回文

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

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

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

我們來(lái)分析一下切割，其實(shí)切割問(wèn)題類(lèi)似組合問(wèn)題。

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

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

感受出來(lái)了不?

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

分割回文串

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

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

回溯三部曲

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

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

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

在39. 組合總和中我們深入探討了組合問(wèn)題什么時(shí)候需要startIndex，什么時(shí)候不需要startIndex。

代碼如下：

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

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

分割回文串

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

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

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

所以終止條件代碼如下：

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

• 單層搜索的邏輯

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

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

首先判斷這個(gè)子串是不是回文，如果是回文，就加入在vector path中，path用來(lái)記錄切割過(guò)的回文子串。

代碼如下：

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 {                // 如果不是則直接跳過(guò) 
        continue; 
    } 
    backtracking(s, i + 1); // 尋找i+1為起始位置的子串 
    path.pop_back();        // 回溯過(guò)程，彈出本次已經(jīng)填在的子串 
} 

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

判斷回文子串

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

可以使用雙指針?lè)?，一個(gè)指針從前向后，一個(gè)指針從后先前，如果前后指針?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; 
} 

如果大家對(duì)雙指針?lè)ㄓ猩枇耍瑐魉烷T(mén)：雙指針?lè)ǎ嚎偨Y(jié)篇!

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

C++整體代碼

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

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

不難寫(xiě)出如下代碼：

class Solution { 
private: 
    vector<vector<string>> result; 
    vector<string> path; // 放已經(jīng)回文的子串 
    void backtracking (const string& s, int startIndex) { 
        // 如果起始位置已經(jīng)大于s的大小，說(shuō)明已經(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 {                                // 不是回文，跳過(guò) 
                continue; 
            } 
            backtracking(s, i + 1); // 尋找i+1為起始位置的子串 
            path.pop_back(); // 回溯過(guò)程，彈出本次已經(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上是中等，但可以說(shuō)是hard的題目了，但是代碼其實(shí)就是按照模板的樣子來(lái)的。

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

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

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

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

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

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

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

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

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

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

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

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

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