C++怎么實(shí)現(xiàn)拆分回文串

這篇文章主要介紹“C++怎么實(shí)現(xiàn)拆分回文串”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“C++怎么實(shí)現(xiàn)拆分回文串”文章能幫助大家解決問題。

Palindrome Partitioning 拆分回文串

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]

這又是一道需要用DFS來解的題目，既然題目要求找到所有可能拆分成回文數(shù)的情況，那么肯定是所有的情況都要遍歷到，對于每一個子字符串都要分別判斷一次是不是回文數(shù)，那么肯定有一個判斷回文數(shù)的子函數(shù)，還需要一個DFS函數(shù)用來遞歸，再加上原本的這個函數(shù)，總共需要三個函數(shù)來求解。我們將已經(jīng)檢測好的回文子串放到字符串?dāng)?shù)組out中，當(dāng)s遍歷完了之后，將out加入結(jié)果res中。那么在遞歸函數(shù)中我們必須要知道當(dāng)前遍歷到的位置，用變量start來表示，所以在遞歸函數(shù)中，如果start等于字符串s的長度，說明已經(jīng)遍歷完成，將out加入結(jié)果res中，并返回。否則就從start處開始遍歷，由于不知道該如何切割，所以我們要遍歷所有的切割情況，即一個字符，兩個字符，三個字符，等等。。首先判斷取出的子串是否是回文串，調(diào)用一個判定回文串的子函數(shù)即可，這個子函數(shù)傳入了子串的起始和終止的范圍，若子串是回文串，那么我們將其加入out，并且調(diào)用遞歸函數(shù)，此時start傳入 i+1，之后還要恢復(fù)out的狀態(tài)。

那么，對原字符串的所有子字符串的訪問順序是什么呢，如果原字符串是 abcd, 那么訪問順序?yàn)? a -> b -> c -> d -> cd -> bc -> bcd-> ab -> abc -> abcd, 這是對于沒有兩個或兩個以上子回文串的情況。那么假如原字符串是 aabc，那么訪問順序?yàn)椋篴 -> a -> b -> c -> bc -> ab -> abc -> aa -> b -> c -> bc -> aab -> aabc，中間當(dāng)檢測到aa時候，發(fā)現(xiàn)是回文串，那么對于剩下的bc當(dāng)做一個新串來檢測，于是有 b -> c -> bc，這樣掃描了所有情況，即可得出最終答案，代碼如下：

解法一：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> out;
        helper(s, 0, out, res);
        return res;
    }
    void helper(string s, int start, vector<string>& out, vector<vector<string>>& res) {
        if (start == s.size()) { res.push_back(out); return; }
        for (int i = start; i < s.size(); ++i) {
            if (!isPalindrome(s, start, i)) continue;
            out.push_back(s.substr(start, i - start + 1));
            helper(s, i + 1, out, res);
            out.pop_back();
        }
    }
    bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) return false;
            ++start; --end;
        }
        return true;
    }
};

我們也可以不單獨(dú)寫遞歸函數(shù)，而是使用原函數(shù)本身來遞歸。首先判空，若字符串s為空，則返回一個包有空字符串?dāng)?shù)組的數(shù)組，注意這里不能直接返回一個空數(shù)組，后面會解釋原因。然后我們從0開始遍歷字符串s，因?yàn)槭鞘褂迷瘮?shù)當(dāng)遞歸，所以無法傳入起始位置start，所以只能從默認(rèn)位置0開始，但是我們的輸入字符串s是可以用子串來代替的，這樣就相當(dāng)于起始位置start的作用。首先我們還是判斷子串是否為回文串，這里的判斷子串還是得用一個子函數(shù)，由于起點(diǎn)一直是0，所以只需要傳一個終點(diǎn)位置即可。如果子串是回文串，則對后面的整個部分調(diào)用遞歸函數(shù)，這樣我們會得到一個二維數(shù)組，是當(dāng)前子串之后的整個部分拆分為的回文串的所有情況，那么我們只需將當(dāng)前的回文子串加入到返回的這些所有情況的集合中?，F(xiàn)在解釋下之前說的為啥當(dāng)字符串s為空的時候，要返回一個帶有空數(shù)組的數(shù)組，這是因?yàn)楫?dāng)子串就是原字符串s的時候，而是還是個回文串，那么后面部分就為空了，若我們對空串調(diào)用遞歸返回的是一個空數(shù)組，那么就無法對其進(jìn)行遍歷，則當(dāng)前的回文串就無法加入到結(jié)果res之中，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if (s.empty()) return {{}};
        for (int i = 0; i < s.size(); ++i) {
            if (!isPalindrome(s, i + 1)) continue;
            for (auto list : partition(s.substr(i + 1))) {
                list.insert(list.begin(), s.substr(0, i + 1));
                res.push_back(list);
            }
        }
        return res;
    }
    bool isPalindrome(string s, int n) {
        for (int i = 0; i < n / 2; ++i) {
            if (s[i] != s[n - 1 - i]) return false;
        }
        return true;
    }
};

下面這種解法是基于解法一的優(yōu)化，我們可以先建立好字符串s的子串回文的dp數(shù)組，光這一部分就可以另出一個道題了 Palindromic Substrings，當(dāng)我們建立好這樣一個二維數(shù)組dp，其中 dp[i][j] 表示 [i, j] 范圍內(nèi)的子串是否為回文串，這樣就不需要另外的子函數(shù)去判斷子串是否為回文串了，大大的提高了計算的效率，豈不美哉？！遞歸函數(shù)的寫法跟解法一中的沒啥區(qū)別，可以看之前的講解，參見代碼如下：

解法三：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> res;
        vector<string> out;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;
                }
            }
        }
        helper(s, 0, dp, out, res);
        return res;
    }
    void helper(string s, int start, vector<vector<bool>>& dp, vector<string>& out, vector<vector<string>>& res) {
        if (start == s.size()) { res.push_back(out); return; }
        for (int i = start; i < s.size(); ++i) {
            if (!dp[start][i]) continue;
            out.push_back(s.substr(start, i - start + 1));
            helper(s, i + 1, dp, out, res);
            out.pop_back();
        }
    }
};

再來看一種迭代的解法，這里還是像上個解法一樣建立判斷字符串s的子串是否為回文串的dp數(shù)組，但建立了一個三維數(shù)組的res，這里的res數(shù)組其實(shí)也可以看作是一個dp數(shù)組，其中 res[i] 表示前i個字符組成的子串，即范圍 [0, i+1] 內(nèi)的子串的所有拆分方法，那么最終只要返回 res[n] 極為所求。然后進(jìn)行for循環(huán)，i 從 0 到 n，j 從 0 到 i，這里我們同時更新了兩個dp數(shù)組，一個是回文串的dp數(shù)組，另一個就是結(jié)果res數(shù)組了，對于區(qū)間 [j, i] 的子串，若其是回文串，則 dp[j][i] 更新為 true，并且遍歷 res[j] 中的每一種組合，將當(dāng)前子串加入，并且存入到 res[i+1] 中，參見代碼如下：

解法四：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<vector<string>>> res(n + 1);
        res[0].push_back({});
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;
                    string cur = s.substr(j, i - j + 1);
                    for (auto list : res[j]) {
                        list.push_back(cur);
                        res[i + 1].push_back(list);
                    }
                }
            }
        }
        return res[n];
    }
};

關(guān)于“C++怎么實(shí)現(xiàn)拆分回文串”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。