131. 分割回文串

給你一個(gè)字符串?s，請你將?s?分割成一些子串，使每個(gè)子串都是?回文串?。返回?s?所有可能的分割方案。

回文串?是正著讀和反著讀都一樣的字符串。

示例 1：

輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]

示例 2：

輸入：s = "a"
輸出：[["a"]]

提示：

• 1 <= s.length <= 16
• s?僅由小寫英文字母組成

思路

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

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

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

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

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

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

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

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

感受出來了不？

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

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

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

#回溯三部曲

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

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

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

在回溯算法：求組合總和（二）?(opens new window)中我們深入探討了組合問題什么時(shí)候需要startIndex，什么時(shí)候不需要startIndex。

代碼如下：

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

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

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

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

在處理組合問題的時(shí)候，遞歸參數(shù)需要傳入startIndex，表示下一輪遞歸遍歷的起始位置，這個(gè)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] 就是要截取的子串。

首先判斷這個(gè)子串是不是回文，如果是回文，就加入在vector<string> 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。

#判斷回文子串

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

可以使用雙指針法，一個(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;
 }

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

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

根據(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;
    }
};

?

• 時(shí)間復(fù)雜度: O(n * 2^n)
• 空間復(fù)雜度: O(n^2)

#優(yōu)化

上面的代碼還存在一定的優(yōu)化空間, 在于如何更高效的計(jì)算一個(gè)子字符串是否是回文字串。上述代碼isPalindrome函數(shù)運(yùn)用雙指針的方法來判定對于一個(gè)字符串s, 給定起始下標(biāo)和終止下標(biāo), 截取出的子字符串是否是回文字串。但是其中有一定的重復(fù)計(jì)算存在:

例如給定字符串"abcde", 在已知"bcd"不是回文字串時(shí), 不再需要去雙指針操作"abcde"而可以直接判定它一定不是回文字串。

具體來說, 給定一個(gè)字符串s, 長度為n, 它成為回文字串的充分必要條件是s[0] == s[n-1]且s[1:n-1]是回文字串。

大家如果熟悉動(dòng)態(tài)規(guī)劃這種算法的話, 我們可以高效地事先一次性計(jì)算出, 針對一個(gè)字符串s, 它的任何子串是否是回文字串, 然后在我們的回溯函數(shù)中直接查詢即可, 省去了雙指針移動(dòng)判定這一步驟.

具體參考代碼如下:

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path; // 放已經(jīng)回文的子串
    vector<vector<bool>> isPalindrome; // 放事先計(jì)算好的是否回文子串的結(jié)果
    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[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)添加的子串
        }
    }
    void computePalindrome(const string& s) {
        // isPalindrome[i][j] 代表 s[i:j](雙邊包括)是否是回文字串 
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); // 根據(jù)字符串s, 刷新布爾矩陣的大小
        for (int i = s.size() - 1; i >= 0; i--) { 
            // 需要倒序計(jì)算, 保證在i行時(shí), i+1行已經(jīng)計(jì)算好了
            for (int j = i; j < s.size(); j++) {
                if (j == i) {isPalindrome[i][j] = true;}
                else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}
                else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        computePalindrome(s);
        backtracking(s, 0);
        return result;
    }
};

?

#總結(jié)

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

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

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

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

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

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

本題我相信很多同學(xué)主要卡在了第一個(gè)難點(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)該叫做無招勝有招，人碼合一。文章來源地址http://www.zghlxwxcb.cn/news/detail-809252.html

到了這里，關(guān)于C++力扣題目131--分割回文串的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！