宜昌网站seo,win7 iis配置网站 视频教程,网站建设交流群,微网站 pc网站同步文章目录1. 题目2. 解题2.1 超时2.2 预处理优化1. 题目
给你一个字符串 s #xff0c;请你找到 s 中两个 不相交回文子序列 #xff0c;使得它们长度的 乘积最大 。 两个子序列在原字符串中如果没有任何相同下标的字符#xff0c;则它们是 不相交 的。
请你返回两个回文子…
文章目录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 (1n)-1;for(int i state; i; istate(i-1)){int left ~istate;for(int k left; k; kleft(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(1i))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 ans1;else return ans;}
};2.2 预处理优化
对于判断是否是回文的操作预先进行处理
class Solution {
public:int maxProduct(string s) {int n s.size();vectorint palind process(s);int ans 1, state (1n)-1;for(int i state; i; istate(i-1)){int left ~istate;for(int k left; k; kleft(k-1))ans max(ans, palind[i]*palind[k]);}return ans;}vectorint process(string s){int n s.size();vectorint palind(1n, 0); for(int state (1n)-1; state; state--){string t;for(int i 0; i n; i){if(state(1i))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] ans1;else palind[state] ans;}return palind;}
};128 ms 7.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
