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){ int n = s.size(); if(n == 0) return 0; vector<int> memo(n+1,-1); memo[0] = 1; memo[1] = s[0] == ‘0‘ ? 0:1; for(int i = 2; i <= n; i++){ if(s[i-1] == ‘0‘){ if(s[i-2] == ‘1‘ || s[i-2] == ‘2‘){ memo[i] = memo[i-2]; } else{ memo[i] = 0; } } else { if(s[i-2] == ‘1‘ || (s[i-2] == ‘2‘ && s[i-1] <= ‘6‘)){ memo[i] = memo[i-1] + memo[i-2]; } else { memo[i] = memo[i-1]; } } } } };
参考：
1，https://blog.csdn.net/u013250416/article/details/80558542
原文：https://www.cnblogs.com/hujianglang/p/12222378.html