[Algorithm] Leetcode #91 Decode Ways (DP/Medium/C++) — How to solve ANY DP

Unsplash

Problem Link: https://leetcode.com/problems/decode-ways/

Hello! Today we’ll be looking at a dynamic programming question: Decode Ways. I found out that many people find this question hard. I will be demonstrating my thought process as well as the detailed explanation.

Before getting into the explanation, I really want to talk about the crux of Dynamic Programming: “How to solve any DP problem?”. I, of course, cannot solve every single DP question out there but I’ve got much better than before by understanding the core concept of DP.

Before you start writing codes, set up a clear recurrence relation(top-down)

As you’ve seen in my previous posts, this is the most important step to solve ANY dynamic programming question and at the same time, this is the most difficult step. Remember that the dynamic programming technique is to optimize a recursion by memoization(or tabulation). There isn’t a single recurrence relation but you can set up any VALID recurrence relation which clearly demonstrates the optimal substructure and repeating subproblems. Once you set up your recurrence relation, you must stick to the very definition of it(I’ll show you what I mean by this). Otherwise, you’ll end up getting a big fat “Wrong Answer” or some type of error message.

With that being said, let’s jump into our problem. Assuming you have fully understood the problem, what’s the first thing you must do? Yes, “Recurrence Relation”!!

• Step I) Grab intuitions from the question to set up a recurrence relation
  - My first intuition is that for a single character, we only have TWO options. Either decode it as a 1)single number or 2) the last digit of a two-digit number(like “19”)
  - For example, in this case [1224], “4” can be decoded into a single “4” or “24”.
  - For the second option, we must constrain with a proper condition. Since a valid number representation of an alphabet is 0–26, only 10~26 is a valid number with two digits.
• Step II) Set up the recurrence relation
  - Let dp[i][twoDigit] = # of ways to decode the string for the range [0,i] while the current character s[i] is the “first digit” or the "two-digit" number (ex. “2”5)
  - I first made a mistake by setting up d[i] = # of ways to decode for [0,i] without considering whether we’re decoding as a single number or two-digit number which later gave me a big fat error.
• Step III) Mingle your intuitions together to code + conditions
  - I used the “carry” variable to carry the current character to the next(i-1) recursive state in the case of “two-digit decoding” so that we can determine if the two-digit number is within the boundary (10~26)
  - if s[i]==0, there is no way for us to make it as a single-digit number, so dp[i][twoDigit] = dp[i-1][true]
  - Else, dp[i][twoDigit] = dp[i-1][true] + dp[i-1][false]
- When the “carry” is present, we must decode the current character as the first digit of the two-digit number(ex, “2"6). Hence, intify the concatenation of current character + carry.
• Step IV) Boundary Case
  - If i<0, return 1 since we have successfully gone through all the cases which means we now have one way to decode(Note that this is against our definition but it does not affect the overall logic. Sometimes, you would need to manipulate the boundary case)

Implementation

Leetcode #91 Decode Ways

Time Complexity: O(n)

If you have any concerns or questions regarding DP or other problems, feel free to send me a message or email below!

[Contact]
✅ Email: changjin9792@gmail.com
✅ Github: https://github.com/JasonLee-cp
✅ Medium: https://changjin9792.medium.com/