[C++]LeetCode: 55 Decode Ways
时间:2022-03-24 18:43
题目:
A message containing letters from for(int i = 2; i <= len; i++)
{
if(s[i-1] != '0')
dp[i] = dp[i-1];
else dp[i] = 0;
if(s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6'))
dp[i] += dp[i-2];
}
4. 动态方程的递推方式,以及dp[i]的含义确定,需要准确和考虑全面。
复杂度:O(N)
AC Code:
class Solution { public: int numDecodings(string s) { int len = s.length(); if(len == 0) return 0; //dp[i]表示s[0,1,...,i-1]的解码方法数目 int dp[len+1]; //初始化dp[0],dp[1] dp[0] = 1; if(s[0] != '0') { dp[1] = 1; } else { dp[1] = 0; } for(int i = 2; i <= len; i++) { //如果末尾数字为无效0,则dp为0 if(isValid(s.substr(i-1, 1))) { dp[i] = dp[i-1]; } else { dp[i] = 0; } if(isValid(s.substr(i-2, 2))) { dp[i] += dp[i-2]; } } return dp[len]; } public: bool isValid(string str) { //如果str中含无效的0,如“02”,解码失败 if(str[0] == '0') return false; int num = std::stoi(str); if(num >= 1 && num <= 26) { return true; } else { return false; } } };