How do you solve Decode Ways II on LeetCode?

Decode Ways II (LeetCode #639) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Handling '*' properly is crucial as it can represent multiple digits.

What is the brute force solution for Decode Ways II?

The brute force approach for Decode Ways II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible combinations of valid decodings for the given string. We can recursively explore each character and its possible interpretations, including handling '*' characters as any digit from '1' to '9'. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Decode Ways II?

Decode Ways II uses the following concepts: String, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Recursion.

What are the interview tips for Decode Ways II?

Always clarify how to handle special characters like '*' before diving into coding. Think about edge cases, such as strings starting or ending with '0' or '*'. Explain your thought process clearly while coding to demonstrate your understanding.

What are common mistakes when solving Decode Ways II?

Forgetting to handle '0' correctly, which cannot be decoded alone. Not considering the impact of '*' on two-digit combinations.

#639

Decode Ways II

Hard

StringDynamic ProgrammingDynamic ProgrammingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to store the number of ways to decode the string up to each index. This avoids redundant calculations by building on previously computed results, making it efficient.

⚙️

Algorithm

3 steps

1Step 1: Initialize a dp array where dp[i] represents the number of ways to decode the substring up to index i.
2Step 2: Set dp[0] to 1 (an empty string has one way to decode).
3Step 3: Iterate through the string and update dp[i] based on the current character and the previous character, considering '*' appropriately.

solution.py19 lines

1def numDecodings(s):
2    MOD = 10**9 + 7
3    n = len(s)
4    dp = [0] * (n + 1)
5    dp[0] = 1
6    for i in range(1, n + 1):
7        if s[i - 1] == '*':
8            dp[i] = (dp[i - 1] * 9) % MOD
9        else:
10            dp[i] = dp[i - 1] if s[i - 1] != '0' else 0
11        if i > 1:
12            if s[i - 2] == '*':
13                if s[i - 1] <= '6':
14                    dp[i] = (dp[i] + dp[i - 2] * 2) % MOD
15                else:
16                    dp[i] = (dp[i] + dp[i - 2]) % MOD
17            elif 10 <= int(s[i - 2:i]) <= 26:
18                dp[i] = (dp[i] + dp[i - 2]) % MOD
19    return dp[n]

ℹ

Complexity note: The time complexity is O(n) because we iterate through the string once, and the space complexity is O(n) due to the dp array storing results for each index.

1Handling '*' properly is crucial as it can represent multiple digits.
2Dynamic programming allows us to build solutions incrementally and avoid redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.