Leetcode Problem 91. Decode Ways

91. Decode Ways

Leetcode Solutions

Approach: Recursive Approach with Memoization

  1. Define a helper function that takes the string s and the current index index as arguments, along with a memoization dictionary memo.
  2. If index is equal to the length of s, return 1 as we have found a valid way to decode the entire string.
  3. If the character at index is '0', return 0 as it cannot lead to a valid decoding.
  4. If the current index is already in memo, return the stored result to avoid redundant calculations.
  5. Initialize a variable ans to store the number of decodings.
  6. Recursively call the helper function with index + 1 to consider single digit decoding and add the result to ans.
  7. If the next two digits form a valid encoding (i.e., between 10 and 26), recursively call the helper function with index + 2 to consider double digit decoding and add the result to ans.
  8. Store the result in memo with the key as the current index.
  9. Return ans.
UML Thumbnail

Approach: Iterative Approach with Dynamic Programming

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...