639. Decode Ways II

639. Decode Ways II

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'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:

Input: "*"Output: 9Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".

Example 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’.

Algorithm：

In the last approach, we can observe that only the last two values dp[i-2]dp[i−2] and dp[i-1]dp[i−1] are used to fill the entry at dp[i-1]dp[i−1]. We can save some space in the last approach, if instead of maintaining a whole dpdp array of length nn, we keep a track of only the required last two values. The rest of the process remains the same as in the last approach.

class Solution { int M = 1000000007; public int numDecodings(String s) { long first = 1, second = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1; for (int i = 1; i < s.length(); i++) { long temp = second; if (s.charAt(i) == '*') { second = 9 * second; if (s.charAt(i - 1) == '1') second = (second + 9 * first) % M; else if (s.charAt(i - 1) == '2') second = (second + 6 * first) % M; else if (s.charAt(i - 1) == '*') second = (second + 15 * first) % M; } else { second = s.charAt(i) != '0' ? second : 0; if (s.charAt(i - 1) == '1') second = (second + first) % M; else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6') second = (second + first) % M; else if (s.charAt(i - 1) == '*') second = (second + (s.charAt(i) <= '6' ? 2 : 1) * first) % M; } first = temp; } return (int) second; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。