Leetcode - Decode Ways

Question

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Idea First Thoughts

• Choice
  • Use current number alone
  • Use current number with next number
  • 26 is the max so double digits are the only options
• if our choice is within the range of 1-26, add one to our result
• Iterate through the integer using 2 points (l, r), check l and then l + r for being in this range and then add to result Correct Idea
• Turns out its similar to a Leetcode - House Robber problem where we can do a top down solution with a cache to keep track of our sub problems
• The sub problem here is decoding the remaining string after we made our binary decision
• Our decision (dp of i+1 or dp of i+2) is:
  • Using the current number alone
    • Need to make sure we don’t start with a 0
  • Using the current number with the next number
    • If the first number is 1, the second number can be 0-9, if it is 2, the second number can be 0-6

Solution