LeetCode 91. Decode Ways
思路:DP
- 状态表示:状态表示:f[i] i个数(最后一个数字是s[i-1])解码得到的所有字符串的数量 f[i]从0开始
- 状态计算:集合可以分成:最后一个i是一位数,和最后一个i是两位数
- 参考: yxc
题目
/*
* @lc app=leetcode id=91 lang=cpp
*
* [91] Decode Ways
*
* https://leetcode.com/problems/decode-ways/description/
*
* algorithms
* Medium (22.71%)
* Likes: 1630
* Dislikes: 1878
* Total Accepted: 288.6K
* Total Submissions: 1.3M
* Testcase Example: '"12"'
*
* A message containing letters from A-Z is being encoded to numbers using the
* following mapping:
*
*
* 'A' -> 1
* 'B' -> 2
* ...
* 'Z' -> 26
*
*
* Given a non-empty string containing only digits, determine the total number
* of ways to decode it.
*
* Example 1:
*
*
* Input: "12"
* Output: 2
* Explanation: It could be decoded as "AB" (1 2) or "L" (12).
*
*
* Example 2:
*
*
* Input: "226"
* Output: 3
* Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2
* 6)
*
*/
代码
class Solution {
public:
int numDecodings(string s) {
// 思路:
// 状态表示:f[i] i个数(最后一个数字是s[i-1])解码得到的所有字符串的数量 f[i]从0开始
// 状态计算: 集合可以分成:最后一个i是一位数,和最后一个i是两位数
// 之前想过的错误思路:f[i] 表示以i结尾的decode共有多少种解法
// 集合划分为不算i:f[i - j] + f[j] 和算i: f[i];
int n = s.size();
vector<int> f(n + 1); //加一是为了方便边界特判
f[0] = 1; //空字符串特判
// 如果最后一个i是个位数 1 ~ 26
// 难点:如何转化char为int
for (int i = 1; i <= n; i ++ ) //从一开始是因为表示的是前多少个字母,不是下标从一开始的字母
{
//如果最后一个i是个位数,且不为0
if (s[i - 1] != '0') f[i] += f[i - 1]; //求数量一般用+=
//如果最后一个i是两位数,且在1~26之间
if (i >= 2)
{
int t = (s[i - 2] -'0') * 10 + s[i - 1] - '0';
if (t >= 10 && t <= 26) f[i] += f[i - 2];
}
}
return f[n];
}
};
同学,为什么将第
i
个数字单独翻译成字母,方案数是f[i - 1]
?将第
i - 1
和第i
个数字一起翻译成字母,方案数是f[i - 2]
?空字符串为什么要特判为1 啊
因为dp是一步步递推过来的,要有初始条件,如果不特判为1的话,
f[0] = 0
, 这样代码运行结果就变为f[1] += f[0] = 0
, 进而f[2] += f[1] = 0
, 举例子来说,input:12
,f[2]
的结果就是0
了