Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/639.html

639. Decode Ways II (Hard)

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: 9
Explanation: 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:

  1. The length of the input string will fit in range [1, 105].
  2. The input string will only contain the character '*' and digits '0' - '9'.

Related Topics:
Dynamic Programming

Similar Questions:

Solution 1. DP

// OJ: https://leetcode.com/problems/decode-ways-ii/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/decode-ways-ii/solution/
class Solution {
    void add(long &a, long b) { a = (a + b) % ((int)1e9+7); }
public:
    int numDecodings(string s) {
        long prev1 = s[0] == '*' ? 9 : (s[0] != '0'), prev2 = 1;
        for (int i = 1; i < s.size(); ++i) {
            long cur = 0;
            if (s[i] == '*') {
                cur = 9 * prev1;
                if (s[i - 1] == '1') add(cur, 9 * prev2);
                else if (s[i - 1] == '2') add(cur, 6 * prev2);
                else if (s[i - 1] == '*') add(cur, 15 * prev2);
            } else {
                cur = s[i] != '0' ? prev1 : 0;
                if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) add(cur, prev2);
                else if (s[i - 1] == '*') add(cur, (s[i] <= '6' ? 2 : 1) * prev2);
            }
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

Java

  • class Solution {
        public int numDecodings(String s) {
            if (s == null || s.length() == 0)
                return 0;
            final int MODULO = 1000000007;
            int length = s.length();
            long[] dp = new long[length + 1];
            dp[length] = 1;
            dp[length - 1] = s.charAt(length - 1) == '0' ? 0 : s.charAt(length - 1) == '*' ? 9 : 1;
            for (int i = length - 2; i >= 0; i--) {
                if (s.charAt(i) == '0')
                    dp[i] = 0;
                else {
                    char c1 = s.charAt(i), c2 = s.charAt(i + 1);
                    if (c1 == '*' && c2 == '*') {
                        int twos = 0;
                        for (int j = 1; j <= 9; j++) {
                            for (int k = 1; k <= 9; k++) {
                                int num = j * 10 + k;
                                if (num <= 26)
                                    twos++;
                            }
                        }
                        dp[i] = 9 * dp[i + 1] + twos * dp[i + 2];
                    } else if (c1 == '*') {
                        int twos = 0;
                        for (int num = 10 + c2 - '0'; num < 100; num += 10) {
                            if (num <= 26)
                                twos++;
                        }
                        dp[i] = 9 * dp[i + 1] + twos * dp[i + 2];
                    } else if (c2 == '*') {
                        int twos = 0;
                        int low = (c1 - '0') * 10 + 1, high = (c1 - '0') * 10 + 9;
                        for (int num = low; num <= high; num++) {
                            if (num <= 26)
                                twos++;
                        }
                        dp[i] = dp[i + 1] + twos * dp[i + 2];
                    } else {
                        int num = Integer.parseInt(s.substring(i, i + 2));
                        dp[i] = num <= 26 ? dp[i + 1] + dp[i + 2] : dp[i + 1];
                    }
                }
                dp[i] %= MODULO;
            }
            return (int) dp[0];
        }
    }
    
  • // OJ: https://leetcode.com/problems/decode-ways-ii/
    // Time: O(N)
    // Space: O(1)
    // Ref: https://leetcode.com/problems/decode-ways-ii/solution/
    class Solution {
        void add(long &a, long b) { a = (a + b) % ((int)1e9+7); }
    public:
        int numDecodings(string s) {
            long prev1 = s[0] == '*' ? 9 : (s[0] != '0'), prev2 = 1;
            for (int i = 1; i < s.size(); ++i) {
                long cur = 0;
                if (s[i] == '*') {
                    cur = 9 * prev1;
                    if (s[i - 1] == '1') add(cur, 9 * prev2);
                    else if (s[i - 1] == '2') add(cur, 6 * prev2);
                    else if (s[i - 1] == '*') add(cur, 15 * prev2);
                } else {
                    cur = s[i] != '0' ? prev1 : 0;
                    if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) add(cur, prev2);
                    else if (s[i - 1] == '*') add(cur, (s[i] <= '6' ? 2 : 1) * prev2);
                }
                prev2 = prev1;
                prev1 = cur;
            }
            return prev1;
        }
    };
    
  • '''
    >>> 1e9
    1000000000.0
    >>> int(1e9 + 7)
    1000000007
    
    1e9 is a method of writing the number 1,000,000,000 in scientific notation, and is short for 1*(10^9)'''
    class Solution:
        def numDecodings(self, s: str) -> int:
            mod = int(1e9 + 7)
            n = len(s)
    
            # dp[i - 2], dp[i - 1], dp[i]
            a, b, c = 0, 1, 0
            for i in range(1, n + 1):
                # 1 digit
                if s[i - 1] == "*":
                    c = 9 * b % mod
                elif s[i - 1] != "0":
                    c = b
                else:
                    c = 0
    
                # 2 digits
                if i > 1:
                    if s[i - 2] == "*" and s[i - 1] == "*":
                        c = (c + 15 * a) % mod
                    elif s[i - 2] == "*":
                        if s[i - 1] > "6":
                            c = (c + a) % mod
                        else:
                            c = (c + 2 * a) % mod
                    elif s[i - 1] == "*":
                        if s[i - 2] == "1":
                            c = (c + 9 * a) % mod
                        elif s[i - 2] == "2":
                            c = (c + 6 * a) % mod
                    elif (
                        s[i - 2] != "0"
                        and (ord(s[i - 2]) - ord("0")) * 10 + ord(s[i - 1]) - ord("0") <= 26
                    ):
                        c = (c + a) % mod
    
                a, b = b, c
    
            return c
    
    ############
    
    # ref: https://leetcode.com/problems/decode-ways-ii/discuss/105262/Python-6-lines-DP-solution
    
    one = {str(i): 1 for i in range(1, 10)}
    one.update({'*': 9, '0': 0})
    
    two = {str(i): 1 for i in range(10, 27)}
    two.update({'*' + str(i): 2 if i <= 6 else 1 for i in range(10)})
    two.update({'1*': 9, '2*': 6, '**': 15})
    
    
    class Solution:
        def numDecodings(self, s):
            dp = (1, one.get(s[:1], 0))
    
            for i in range(1, len(s)):
                dp = (dp[1], (one.get(s[i]) * dp[1] + two.get(s[i - 1: i + 1], 0) * dp[0]) % 1000000007)
    
            return dp[-1]
    
    

All Problems

All Solutions