Palindrome Partitioning

原題鏈接Palindrome Partitioning

對字符串進行切分，使得切分出的每個子串都是回文串，返回所有的切分可能

對于每個字符都可能在它的位置切分，所以可以容易想到使用深度優先和回溯法求解。另外，為了避免重復判斷，采用動態規劃的思想記錄某個字符是否已經判斷過

代碼如下

class Solution { public:vector<vector<string>> partition(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n, -1));vector<vector<string>> res;vector<string> cur;partition(s, 0, cur, res, dp);return res;} private:/* 尋找s[idx : s.size()-1]這個字符串的切分結果 */void partition(string& s, int idx, vector<string>& cur, vector<vector<string>>& res, vector<vector<int>>& dp){if(idx >= s.size()){res.emplace_back(cur);return;}/* 將s[idx : s.size()-1]切分成s[idx : i]和s[i+1 : s.size()-1] */for(int i = idx; i < s.size(); ++i){if(dp[idx][i] == 0) continue;if(dp[idx][i] == 1 || isPalindrome(s, idx, i)){dp[idx][i] = 1;cur.emplace_back(s.substr(idx, i - idx + 1));partition(s, i + 1, cur, res, dp);cur.pop_back();}else{dp[idx][i] = 0;}}}bool isPalindrome(string& s, int start, int end){while(start < end){if(s[start++] != s[end--])return false;}return true;} };

---

Palindrome Partitioning II

原題鏈接Palindrome Partitioning II

計算最少需要切分多少次才可以切分出每個都是回文串的情況

通常計算次數的問題都不會按照計算所有可能結果那樣求解，所以本題也不會像上面的方法那樣計算次數。不過切分的方法還是不變的，在每個可能的位置切分

對于源字符串s[i : n-1]，對于i<=j<=n?1的ｋ，將其在j處切分得到s[i : j]和s[j+1 : n-1]。不過也不是對于所有的j都這樣做，因為切分是需要滿足回文規則的，需要s[i : j]是回文串

令count[i]表示s[i : n-1]這個子串最少需要切多少次才可以切成多個回文子串(n是字符串s的長度)，那么有count[i]=min(count[i],1+count[j+1])

上式說明將字符串s[i : n-1]在j處切分，同時滿足s[i : j]是回文串，那么總次數就是在k處切分的1次加上后半部分字符串的切分次數

代碼如下

class Solution { public:int minCut(string s) {if(s.empty()) return 0;int n = s.size();/* p[i][j]表示s[i : j]是否是回文串 */vector<vector<int>> p(n, vector<int>(n, 0));/* count[i]表示s[i : n-1]的最少切分次數 */vector<int> count(n, 0);for(int i = n - 1; i >= 0; --i){/* 沒有計算之前，最小的次數就是全切分次數 */count[i] = n - 1 - i;/* 從后面每個位置都可以切分 */for(int j = i; j < n; ++j){/* 只有兩邊相等且中間是回文串時，加入s[j]后s[i : j]才是回文串 */if(s[i] == s[j] && (j - i <= 2 || p[i + 1][j - 1] == 1)){p[i][j] = 1;/* j == n -1代表s[i : n-1]是回文串，不需要切分 */if(j == n - 1)count[i] = 0;/* 更新最小次數 */else if(count[i] > 1 + count[j + 1])count[i] = 1 + count[j + 1];}}}return count[0];} };

第一題主要利用回溯法，類似的求解所有可能的結果時采用回溯法是比較容易想到的。第二題的動態規劃不太容易想到，如果考慮到子問題的話就好辦了

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----将字符串切分，使每个子串都是回文串，计算所有可能结果和最小切分次数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。