[动态编程] [二分搜索] [删除] 730.计算不同回文的子序列
作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
二分查找算法合集
LeetCode730. 统计不同回文子序列
给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致，那么它是回文序列。
如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, … 和 b1, b2, … 不同。
示例 1：
输入：s = ‘bccb’
输出：6
解释：6 个不同的非空回文子字符序列分别为：‘b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。
注意：‘bcb’ 虽然出现两次但仅计数一次。
示例 2：
输入：s = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 是对 109 + 7 取余后的值。
提示：
1 <= s.length <= 1000
s[i] 仅包含 ‘a’, ‘b’, ‘c’ 或 ‘d’
动态规划
动态规划的转移方程
s[left,right] 中不重复 回文的数量，分类：
- 情况一：长度1的回文： 如果a 出现，则必定有回文a。b,c,d。类似。
- 情况二：长度为2的回文：如果a出现两次则必定有aa。bb或cc或dd类似。
- 情况三：长度为x(x>2)的回文：分四种 a+长度为x-2的回文+a b+长度为x-2的回文+b c+长度为x-2的回文+c d+长度为x-2的回文+d 。如果多个a，取最左、最右的a，b,c,d类似。
first(ch) 是ch在s[left,r]的最小下标，end(ch)是s[left,r]的最大下标。Cnt(ch)表示ch在s[left,r]中出现次数。 转移方程为：
dp[left][right] = Sum′ a ′ , ′ b ′ , ′ c ′ , ′ d ′ c h \Large^{ch}_{'a','b','c','d'}′a′,′b′,′c′,′d′ch(Cnt(ch)>=1 + Cnt(ch)>=2 + dp[first(ch)+1,end(ch)-1]
dp[first(ch)+1,end(ch)-1] 之间不会重复，因为左右各有ch。由于长度不同，所以情况一、情况二、情况三之间不会重复。由于长度不同，不同层次的dp[first(ch)+1,end(ch)-1] 也不会相同。
代码
封装类
template<int MOD = 1000000007> class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; };
核心代码
class Solution { public: int countPalindromicSubsequences(string s) { m_c = s.length(); for (int i = 0; i < s.length(); i++) { m_indexs[s[i] - 'a'].emplace_back(i); } m_dp.assign(m_c, vector<C1097Int<>>(m_c)); m_bDo.assign(m_c, vector<bool>(m_c)); return Cal(0, m_c - 1).ToInt(); } C1097Int<> Cal(const int left, const int r) { if (left> r) { return 0; } if (m_bDo[left][r]) { return m_dp[left][r]; } m_bDo[left][r] = true; C1097Int<> biRet; for (int i = 0; i < 4; i++) { auto it1 = std::lower_bound(m_indexs[i].begin(), m_indexs[i].end(), left); auto it2 = std::upper_bound(m_indexs[i].begin(), m_indexs[i].end(), r); const int iCnt = it2 - it1 ; biRet += min(2, iCnt); if (iCnt >= 2) { biRet += Cal(*it1 + 1, *std::prev(it2) - 1); } } return m_dp[left][r] = biRet; } int m_c; vector<int> m_indexs[4]; vector<vector<C1097Int<>>> m_dp; vector<vector<bool>> m_bDo; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string s; { Solution sln; s = "bccb"; auto res = sln.countPalindromicSubsequences(s); Assert(6, res); } { Solution sln; s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"; auto res = sln.countPalindromicSubsequences(s); Assert(104860361, res); } { Solution sln; s = "dcabdacadbbabdabbacbdbadcacaadddabbdccadbaacdacacaadacccbadaccaddcccabccdcbdccdccaadbbcbcccbaadbccddcdbdbcbbadcdccbcabcddcdbcadcadaccacbdcccaacccbdccdcbbccbdbccbacabdbddaacccdccbaaadbbcdccdbddbbcbaacddbbacdbdcdacddbabdcdcbdcbbbcdcdaacbaacdacadacdcdcdcbdbbbaacccdddddddbbdadcaacaddbabbddccabacccaacbdddccaabbdcdccabadccbcdbdaccdcaadaccdbaaaababddddbdacdbdbaabbabcbbabbabcbadacdbccbbcccabaddddcbadbbadcabdbbddbbaacbdbbbbacdddbcdddbdbdcbcdadcccccdccddacddccbddbacababbbcbcadaddbdddcbddbaadacdbdabbabbbcdbdcccdadcbddbacccbacbcbcdccbadcaabdbacbdcddadcbddcadccddaddcdacdabbcbcdadbaacdadacacadbabcbdcabbdcbdbcbddbcddabbaaabadccdbccddcabddabcdbccaacbabacaccbbaccdcbcbdbcbdbccaddcadaaabcaaaaabcbdcadaacadbbbcdddbaabdcdabdbcacdcaaccdcbabadddddcaabbbacabdadcabdacddcdcadadbddccbabbabbcdbadcccacdcaaaadabcadaabcdaacadccdbbbacddabdadaabcbddcdabcaabbbdcccbcaaabaccbbcbbdbcadcdaadddacdbaccccdbcbbaccadacdbaccadabbbbcabcacabaaccbdcdbaddccdbdbdaacbdbcdadbdaddccbdddaadabdabadbacaabbbbabcdabbcbbddbcaadabadbbdacadadabd"; auto res = sln.countPalindromicSubsequences(s); Assert(369668464, res); } }
2023年1月版
class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (*dst + iSrc) % s_iMod;
}
static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1) { *dst = (*dst + iSrc) % s_iMod; *dst = (*dst + iSrc1) % s_iMod; } static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1, const int& iSrc2) { *dst = (*dst + iSrc) % s_iMod; *dst = (*dst + iSrc1) % s_iMod; *dst = (*dst + iSrc2) % s_iMod; } static void SubAssignment(int* dst, const int& iSrc) { *dst = (s_iMod - iSrc + *dst) % s_iMod; } static int Add(const int& iAdd1, const int& iAdd2) { return (iAdd1 + iAdd2) % s_iMod; } static int Mul(const int& i1, const int& i2) { return((long long)i1 *i2) % s_iMod; }
private:
static const int s_iMod = 1000000007;
};
class Solution {
public:
int countPalindromicSubsequences(string s) {
m_c = s.length();
for (int i = 0; i < 4; i++)
{
m_dp[i].assign(m_c, vector(m_c,-1));
}
int iRet = 0;
for (char ch = ‘a’; ch <= ‘d’; ch++)
{
CBigMath::AddAssignment(&iRet, Rec(ch, s, 0, s.length() - 1));
}
return iRet;
}
int Rec(const char& ch,const string& s, int left, int right)
{
while ((left <= right) && (ch != s[left]))
{
left++;
}
if (left > right)
{
return 0;
}
while ((right > left) && (ch != s[right]))
{
right–;
}
if (left == right)
{
return 1;
}
auto& iNum = m_dp[ch - ‘a’][left][right];
if (-1 != iNum)
{
return iNum;
}
iNum = 2;
for (char ch1 = ‘a’; ch1 <= ‘d’; ch1++)
{
CBigMath::AddAssignment(&iNum, Rec(ch1, s, left + 1, right - 1));
}
return iNum;
}
int m_c;
vector<vector> m_dp[4];
};
2023年6月版
using namespace std;
template
void OutToConsoleInner(const vector& vec,const string& strSep = " ")
{
for (int i = 0; i < vec.size(); i++)
{
if (0 != i%25)
{
std::cout << strSep.c_str();
}
std::cout << setw(3) << setfill(’ ') << vec[i];
if (0 == (i+1) % 25)
{
std::cout << std::endl;
}
else if (0 == (i + 1) % 5)
{
std::cout << strSep.c_str();
}
}
}
class CConsole
{
public :
template<class T> static void Out(const vector<T>& vec, const string& strColSep = " ", const string& strRowSep = "\r\n") { OutToConsoleInner(vec, strColSep); std::cout << strRowSep.c_str(); } template<class T> static void Out(const vector<vector<T>>& matrix, const string& strColSep = " ", const string& strRowSep = "\r\n") { for (int i = 0; i < matrix.size(); i++) { OutToConsoleInner(matrix[i], strColSep); std::cout << strRowSep.c_str(); } } template<class T> static void Out(const std::map<T, std::vector<int> >& mTopPointToPoints, const string& strColSep = " ", const string& strRowSep = "\r\n") { for (auto kv : mTopPointToPoints) { std::cout << kv.first << ":"; OutToConsoleInner(kv.second, strColSep); std::cout << strRowSep.c_str(); } } static void Out(const std::string& t, const string& strColSep = " ", const string& strRowSep = "\r\n") { std::cout << t.c_str() << strColSep.c_str(); } template<class T > static void Out(const T& t, const string& strColSep = " ", const string& strRowSep = "\r\n") { std::cout << t << strColSep.c_str(); }
};
void GenetateSum(vector& sums, const vector& nums)
{
sums.push_back(0);
for (int i = 0; i < nums.size(); i++)
{
sums.push_back(nums[i] + sums[i]);
}
}
//[iBegin，iEnd]之和
long long Total(int iBegin,int iEnd)
{
return (long long)(iBegin + iEnd)*(iEnd - iBegin + 1) / 2;
}
class CLadderhlp
{
public:
CLadderhlp( int ladders)
{
m_uLadderNum = ladders;
}
void AddNeedBick(int iNeedBick)
{
if (0 == m_uLadderNum)
{
return;
}
if (m_ladders.size() < m_uLadderNum)
{
m_ladders.push(iNeedBick);
m_iEaqualBicks += iNeedBick;
return;
}
int iTop = m_ladders.top();
if (iTop >= iNeedBick)
{
return;
}
m_iEaqualBicks -= iTop;
m_iEaqualBicks += iNeedBick;
m_ladders.pop();
m_ladders.push(iNeedBick);
}
std::priority_queue<int,vector,std::greater > m_ladders;
unsigned int m_uLadderNum;
long long m_iEaqualBicks = 0;
};
struct CPeo
{
CPeo(string strName, CPeo* pParent=nullptr)
{
m_strName = strName;
m_pParent = pParent;
}
string m_strName;
<