C++怎么實現拆分回文串

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

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

那么，對原字符串的所有子字符串的訪問順序是什么呢，如果原字符串是 abcd, 那么訪問順序為: a -> b -> c -> d -> cd -> bc -> bcd-> ab -> abc -> abcd, 這是對于沒有兩個或兩個以上子回文串的情況。那么假如原字符串是 aabc，那么訪問順序為：a -> a -> b -> c -> bc -> ab -> abc -> aa -> b -> c -> bc -> aab -> aabc，中間當檢測到aa時候，發現是回文串，那么對于剩下的bc當做一個新串來檢測，于是有 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;
    }
};

我們也可以不單獨寫遞歸函數，而是使用原函數本身來遞歸。首先判空，若字符串s為空，則返回一個包有空字符串數組的數組，注意這里不能直接返回一個空數組，后面會解釋原因。然后我們從0開始遍歷字符串s，因為是使用原函數當遞歸，所以無法傳入起始位置start，所以只能從默認位置0開始，但是我們的輸入字符串s是可以用子串來代替的，這樣就相當于起始位置start的作用。首先我們還是判斷子串是否為回文串，這里的判斷子串還是得用一個子函數，由于起點一直是0，所以只需要傳一個終點位置即可。如果子串是回文串，則對后面的整個部分調用遞歸函數，這樣我們會得到一個二維數組，是當前子串之后的整個部分拆分為的回文串的所有情況，那么我們只需將當前的回文子串加入到返回的這些所有情況的集合中。現在解釋下之前說的為啥當字符串s為空的時候，要返回一個帶有空數組的數組，這是因為當子串就是原字符串s的時候，而是還是個回文串，那么后面部分就為空了，若我們對空串調用遞歸返回的是一個空數組，那么就無法對其進行遍歷，則當前的回文串就無法加入到結果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;
    }
};

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

解法三：

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數組，但建立了一個三維數組的res，這里的res數組其實也可以看作是一個dp數組，其中 res[i] 表示前i個字符組成的子串，即范圍 [0, i+1] 內的子串的所有拆分方法，那么最終只要返回 res[n] 極為所求。然后進行for循環，i 從 0 到 n，j 從 0 到 i，這里我們同時更新了兩個dp數組，一個是回文串的dp數組，另一個就是結果res數組了，對于區間 [j, i] 的子串，若其是回文串，則 dp[j][i] 更新為 true，并且遍歷 res[j] 中的每一種組合，將當前子串加入，并且存入到 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];
    }
};

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