C++實現LeetCode(131.拆分回文串)

Posted on by

[LeetCode] 131.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++實現LeetCode(131.拆分回文串)的文章就介紹到這瞭,更多相關C++實現拆分回文串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：