How hard is LeetCode 639. Decode Ways II?

LeetCode 639. Decode Ways II is rated Hard on LeetCode.

What topics does LeetCode 639. Decode Ways II cover?

LeetCode 639. Decode Ways II is tagged String and Dynamic Programming on LeetCode.

Decode Ways II — LeetCode 639 Python Solution

HardStringDynamic Programming

Problem: #639
Pattern: Dynamic Programming
Reading time: 7 min
Source: leetcode.com

The problem

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways).

Example

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 639. Decode Ways II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 639. Decode Ways II?: LeetCode 639. Decode Ways II is rated Hard on LeetCode.
What topics does LeetCode 639. Decode Ways II cover?: LeetCode 639. Decode Ways II is tagged String and Dynamic Programming on LeetCode.