#91

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Decode Ways

Decode Ways is a dynamic programming problem focused on decoding a numeric string to letters using specific mappings.

Problem Statement

Given a string s consisting of digits, determine how many ways the string can be decoded. Each number between 1 and 26 corresponds to a letter from 'A' to 'Z'. The string may contain leading zeros, and such cases will render the string undecodeable.

For example, '12' can be decoded as 'AB' or 'L', whereas '06' is invalid due to the leading zero. You need to count the number of possible decoding ways that can be obtained from the string s.

Examples

Example 1

Input: s = "12"

Output: 2

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2

Input: s = "226"

Output: 3

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3

Input: s = "06"

Output: 0

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Constraints

1 <= s.length <= 100
s contains only digits and may contain leading zero(s).

Solution Approach

Dynamic Programming Initialization

Initialize two variables, dp[0] and dp[1], where dp[i] represents the number of ways to decode the substring s[0..i-1]. The base case is dp[0] = 1 (the empty string has one way to be decoded). The second base case is dp[1], which is 1 if s[0] is not '0' (since '0' has no valid mapping).

State Transition Logic

Iterate over the string s from index 2 onwards. For each character, check if the single digit at s[i-1] is a valid decoding (i.e., non-zero). If valid, add dp[i-1] to dp[i]. Then, check if the two digits at s[i-2..i-1] form a valid number between 10 and 26; if so, add dp[i-2] to dp[i].

Edge Case Handling

Handle special cases like leading zeros. If a character is '0' or any two-digit number is not between 10 and 26, ensure it is skipped or results in zero ways. This is critical to avoid counting invalid strings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string s, as we iterate over the string once and compute dp values for each character. The space complexity is O(n) due to the dp array storing values for each substring of s.

What Interviewers Usually Probe

Can the candidate identify the base cases for dynamic programming?
Do they account for edge cases like leading zeros or invalid two-digit numbers?
Can the candidate explain how state transitions work in dynamic programming for this problem?

Common Pitfalls or Variants

Common pitfalls

Forgetting to initialize the dp array correctly, especially handling dp[1] when s[0] is '0'.
Not checking if a two-digit number is valid before adding to dp[i].
Misunderstanding the significance of leading zeros and not handling them properly.

Follow-up variants

Considerations for decoding strings with additional constraints like very large numbers.
Alternative approaches using recursion with memoization instead of dynamic programming.
Variation where instead of decoding to letters, the numbers correspond to a different set of symbols or characters.

FAQ

How does dynamic programming apply to the Decode Ways problem?

Dynamic programming is used to efficiently count the number of ways a string can be decoded by storing intermediate results in a dp array. This avoids recalculating the number of decodings for overlapping subproblems.

What is the time complexity of the Decode Ways problem?

The time complexity of this problem is O(n), where n is the length of the input string. The solution iterates over the string once, processing each character in constant time.

Can the Decode Ways problem have invalid strings?

Yes, a string with leading zeros or values outside the range of 1 to 26 cannot be decoded. These cases should be handled explicitly by returning 0 for invalid input.

What is the base case for dynamic programming in Decode Ways?

The base case for dynamic programming is dp[0] = 1, representing the number of ways to decode the empty string. dp[1] is 1 if the first character is not '0'.

Are there any alternate approaches to solve the Decode Ways problem?

Yes, instead of dynamic programming, recursion with memoization could also be used to solve the problem, though it might not be as efficient in terms of space.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ to represent the number of decoding methods for the first $i$ characters of the string. Initially, $f[0]=1$, and the rest $f[i]=0$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0] * n
        for i, c in enumerate(s, 1):
            if c != "0":
                f[i] = f[i - 1]
            if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:
                f[i] += f[i - 2]
        return f[n]

Continue Practicing

#87 scramble string #97 interleaving string #72 edit distance