文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 超時
    • 2.2 預處理優化

1. 題目

給你一個字符串 s ，請你找到 s 中兩個 不相交回文子序列 ，使得它們長度的 乘積最大 。
兩個子序列在原字符串中如果沒有任何相同下標的字符，則它們是 不相交 的。

請你返回兩個回文子序列長度可以達到的 最大乘積 。

子序列 指的是從原字符串中刪除若干個字符（可以一個也不刪除）后，剩余字符不改變順序而得到的結果。如果一個字符串從前往后讀和從后往前讀一模一樣，那么這個字符串是一個 回文字符串 。

示例 1：

輸入：s = "leetcodecom" 輸出：9 解釋：最優方案是選擇 "ete" 作為第一個子序列，"cdc" 作為第二個子序列。 它們的乘積為 3 * 3 = 9 。示例 2： 輸入：s = "bb" 輸出：1 解釋：最優方案為選擇 "b" （第一個字符）作為第一個子序列，"b" （第二個字符）作為第二個子序列。 它們的乘積為 1 * 1 = 1 。示例 3： 輸入：s = "accbcaxxcxx" 輸出：25 解釋：最優方案為選擇 "accca" 作為第一個子序列，"xxcxx" 作為第二個子序列。 它們的乘積為 5 * 5 = 25 。提示： 2 <= s.length <= 12 s 只含有小寫英文字母。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：LeetCode 1178. 猜字謎（狀態壓縮+枚舉二進制子集+哈希）

• 枚舉狀態子集。

2.1 超時

226 / 226 個通過測試用例

class Solution { public:int maxProduct(string s) {int n = s.size();int ans = 1, state = (1<<n)-1;for(int i = state; i; i=state&(i-1)){int left = ~i&state;for(int k = left; k; k=left&(k-1))ans = max(ans, process(s, i)*process(s, k));}return ans;}int process(string& s, int num){int n = s.size();string t;for(int i = 0; i < n; ++i){if(num&(1<<i))t.push_back(s[i]);}int ans = 0, i = 0, j = int(t.size())-1;while(i < j){if(t[i] == t[j]){i++, j--;ans += 2;}elsebreak;}if(i < j) return 0;if(i == j) return ans+1;else return ans;} };

2.2 預處理優化

對于判斷是否是回文的操作預先進行處理

class Solution { public:int maxProduct(string s) {int n = s.size();vector<int> palind = process(s);int ans = 1, state = (1<<n)-1;for(int i = state; i; i=state&(i-1)){int left = ~i&state;for(int k = left; k; k=left&(k-1))ans = max(ans, palind[i]*palind[k]);}return ans;}vector<int> process(string& s){int n = s.size();vector<int> palind(1<<n, 0); for(int state = (1<<n)-1; state; state--){string t;for(int i = 0; i < n; ++i){if(state&(1<<i))t.push_back(s[i]);}int ans = 0, i = 0, j = int(t.size())-1;while(i < j){if(t[i] == t[j]){i++, j--;ans += 2;}elsebreak;}if(i < j) ;if(i == j) palind[state] = ans+1;else palind[state] = ans;}return palind;} };

128 ms 7.1 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2002. 两个回文子序列长度的最大乘积（状态压缩+枚举状态子集+预处理）的全部內容，希望文章能夠幫你解決所遇到的問題。

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