Leetcode Problem 639. Decode Ways II

639. Decode Ways II

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a dp array of size n + 1, where n is the length of the input string s. Set dp[0] to 1 as there is one way to decode an empty string.
  2. Iterate over the string from the first character to the last.
  3. For each character at index i, check if it is a *. If so, multiply dp[i] by 9 as there are 9 possible decodings for *.
  4. Check if the current character can form a valid two-digit number with the previous character. If the previous character is 1, or 2 and the current character is between 0 and 6, or if the previous character is *, update dp[i] accordingly.
  5. If the current character is 0, ensure it forms a valid two-digit number with the previous character; otherwise, it cannot be decoded.
  6. Return dp[n] modulo 10^9 + 7 as the final result.
UML Thumbnail

Recursion with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...