作者推荐
本文涉及知识点
字符串 滚动向量
LeetCode 639. 解码方法 II
一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，“11106” 可以映射为：
“AAJF” 对应分组 (1 1 10 6)
“KJF” 对应分组 (11 10 6)
注意，像 (1 11 06) 这样的分组是无效的，因为 “06” 不可以映射为 ‘F’ ，因为 “6” 与 “06” 不同。
除了 上面描述的数字字母映射方案，编码消息中可能包含 '’ 字符，可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括 ‘0’）。例如，编码字符串 "1" 可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19” 中的任意一条消息。对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s ，由数字和 '’ 字符组成，返回 解码 该字符串的方法 数目 。
由于答案数目可能非常大，返回 109 + 7 的 模 。
示例 1：
输入：s = ""
输出：9
解释：这一条编码消息可以表示 “1”、“2”、“3”、“4”、“5”、“6”、“7”、“8” 或 “9” 中的任意一条。
可以分别解码成字符串 “A”、“B”、“C”、“D”、“E”、“F”、“G”、“H” 和 “I” 。
因此，“" 总共有 9 种解码方法。
示例 2：
输入：s = "1”
输出：18
解释：这一条编码消息可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19” 中的任意一条。
每种消息都可以由 2 种方法解码（例如，“11” 可以解码成 “AA” 或 “K”）。
因此，“1*” 共有 9 * 2 = 18 种解码方法。
示例 3：
输入：s = “2*”
输出：15
解释：这一条编码消息可以表示 “21”、“22”、“23”、“24”、“25”、“26”、“27”、“28” 或 “29” 中的任意一条。
“21”、“22”、“23”、“24”、“25” 和 “26” 由 2 种解码方法，但 “27”、“28” 和 “29” 仅有 1 种解码方法。
因此，“2*” 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。
提示：
1 <= s.length <= 105
s[i] 是 0 - 9 中的一位数字或字符 ‘*’
分析
时间复杂度：O(nm) n=s.length m = 9（1到9)。
动态规划的细节，方便检查
| 动态规划的状态表示 | dp[j]表示s[0,i) 以 j+'A’结尾的合法串数量。dp[0]是占位符，无意义，请忽略 |
| 动态规划的转移方程 | 见下文 |
| 动态规划的初始状态 | 如果是*,dp[1,9]=1，否则dp[s[0]-‘A’]=1 |
| 动态规划的填表顺序 | i从1到大,确保动态规划的无后效性 |
| 动态规划的返回值 | 求和 [ 1 , 26 ] j ^{j}_{[1,26]}[1,26]jdp[j] |
动态规划的转移方程
有两种转移方式：
新建字符： 当前字符必须是[1,9],前一个字符不限。
和前面的串最后一个字符结合：
当前字符：[0,9] 前一字符：1
或
当前字符：[0,6] 前一字符 2
代码
封装类
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 numDecodings(string s) { vector<C1097Int<>> pre(27); if ('*' == s[0]) { for (int i = 1; i <= 9; i++) { pre[i] += 1; } } else { pre[s[0] - '0'] += 1; } for (int i = 1; i < s.length(); i++) { vector<C1097Int<>> dp(27); const auto total = std::accumulate(pre.begin()+1, pre.end(), C1097Int<>()); auto Add = [&dp, &pre,&total](const char& ch) { if ((ch >= '1') && (ch <= '9')) { dp[ch - '0'] += total;//新字符 } dp[ch - '0' + 10] += pre[1]; if ((ch >= '0') && (ch <= '6')) { dp[ch - '0' + 20] += pre[2]; } }; if ('*' == s[i]) { for (char ch = '1'; ch <= '9'; ch++) { Add(ch); } } else { Add(s[i]); } pre.swap(dp); } return std::accumulate(pre.begin() + 1, pre.end(), C1097Int<>()).ToInt(); } };
测试用例
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 = "0"; auto res = sln.numDecodings(s); Assert(0, res); } { Solution sln; s = "*"; auto res = sln.numDecodings(s); Assert(9, res); } { Solution sln; s = "1*"; auto res = sln.numDecodings(s); Assert(18, res); } { Solution sln; s = "2*"; auto res = sln.numDecodings(s); Assert(15, res); } { Solution sln; s = "*********"; auto res = sln.numDecodings(s); Assert(291868912, res); } { Solution sln; s = "**3*******"; auto res = sln.numDecodings(s); Assert(351940699, res); } { Solution sln; s = "*1*3***4**6**"; auto res = sln.numDecodings(s); Assert(632929394, res); } { Solution sln; s = "*1*3***4**6*7*"; auto res = sln.numDecodings(s); Assert(468371306, res); } }
改进
修改了三处：
一，初始化简洁。
二，total 包括dp[0]。
三，i从0开始。
代码更简洁。
class Solution { public: int numDecodings(string s) { vector<C1097Int<>> pre(27); pre[0] = 1; for (int i = 0; i < s.length(); i++) { vector<C1097Int<>> dp(27); const auto total = std::accumulate(pre.begin(), pre.end(), C1097Int<>()); auto Add = [&dp, &pre,&total](const char& ch) { if ((ch >= '1') && (ch <= '9')) { dp[ch - '0'] += total;//新字符 } dp[ch - '0' + 10] += pre[1]; if ((ch >= '0') && (ch <= '6')) { dp[ch - '0' + 20] += pre[2]; } }; if ('*' == s[i]) { for (char ch = '1'; ch <= '9'; ch++) { Add(ch); } } else { Add(s[i]); } pre.swap(dp); } return std::accumulate(pre.begin() + 1, pre.end(), C1097Int<>()).ToInt(); } };
2023年第一版
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 numDecodings(string s) { vector<int> preDp(27); if ('*' == s[0]) { for (int i = 1; i < 10; i++) { preDp[i] = 1; } } else if ('0' != s[0]) { preDp[s[0] - '0'] = 1; } for (int i = 1; i < s.length(); i++) { vector<int> dp(27); if ('*' == s[i]) { for (int j = 1; j < 10; j++) { Test(dp, preDp, j); } } else { Test(dp, preDp, s[i] - '0'); } preDp.swap(dp); } int iRet = 0; for (const auto& p : preDp) { CBigMath::AddAssignment(&iRet, p); } return iRet; } void Test(vector<int>& dp, const vector<int>& preDp, int iNum) { if (0 != iNum) { for (int i = 0; i < preDp.size(); i++) { CBigMath::AddAssignment(&dp[iNum], preDp[i]); } } CBigMath::AddAssignment(&dp[10 + iNum], preDp[1]); if (iNum <= 6) { CBigMath::AddAssignment(&dp[20 + iNum], preDp[2]); } } };
2023年1月第2版
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 numDecodings(string s) {
vector preDp(27);
if (‘’ == s[0])
{
for (int i = 1; i < 10; i++)
{
preDp[i] = 1;
}
}
else if (‘0’ != s[0])
{
preDp[s[0] - ‘0’] = 1;
}
for (int i = 1; i < s.length(); i++)
{
vector dp(27);
if ('’ == s[i])
{
int iTotal = GetTotal(preDp);
for (int j = 1; j < 10; j++)
{
Test(dp, preDp, iTotal,j);
}
}
else
{
int iTotal = GetTotal(preDp);
Test(dp, preDp, iTotal,s[i] - ‘0’);
}
preDp.swap(dp);
}
return GetTotal(preDp);
}
int GetTotal(const vector& preDp)
{
int iRet = 0;
for (const auto& p : preDp)
{
CBigMath::AddAssignment(&iRet, p);
}
return iRet;
}
void Test(vector& dp, const vector& preDp,int iTotal, int iNum)
{
if (0 != iNum)
{
CBigMath::AddAssignment(&dp[iNum], iTotal);
}
CBigMath::AddAssignment(&dp[10 + iNum], preDp[1]);
if (iNum <= 6)
{
CBigMath::AddAssignment(&dp[20 + iNum], preDp[2]);
}
}
};
