Problem:
A message containing letters from A-Z is being encoded to numbers using the following mapping way:
|
1 2 3 4 |
'A' -> 1 'B' -> 2 ... 'Z' -> 26 |
Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
|
1 2 3 4 |
Input: "*" Output: 9 Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I". |
Example 2:
|
1 2 |
Input: "1*" Output: 9 + 9 = 18 |
Note:
- The length of the input string will fit in range [1, 105].
- The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.
Idea:
DP
Time complexity: O(n)
Space complexity: O(1)
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Author: Huahua // Runtime: 58 ms class Solution { public: int numDecodings(string s) { if (s.empty()) return 0; // dp[-1] dp[0] long dp[2] = {1, ways(s[0])}; for (int i = 1; i < s.length(); ++i) { long dp_i = ways(s[i]) * dp[1] + ways(s[i - 1], s[i]) * dp[0]; dp_i %= kMod; dp[0] = dp[1]; dp[1] = dp_i; } return dp[1]; } private: static constexpr int kMod = 1000000007; int ways(char c) { if (c == '0') return 0; if (c == '*') return 9; return 1; } int ways(char c1, char c2) { if (c1 == '*' && c2 == '*') return 15; if (c1 == '*') { return (c2 >= '0' && c2 <= '6') ? 2 : 1; } else if (c2 == '*') { switch (c1) { case '1': return 9; case '2': return 6; default: return 0; } } else { int prefix = (c1 - '0') * 10 + (c2 - '0'); return prefix >= 10 && prefix <= 26; } } }; |
Related Problems: