Solving LeetCode 91. Decode Ways using JavaScript

Tomorrow I take the shared reigns facilitating Flatiron School’s #algo-club as one fearless leader jumps headlong into her first day at her new job, and the other sticks with us for a couple of weeks before he too is off to the working world. To keep sharp for myself and for the club we’ll go over this medium difficulty LeetCode problem, but I will also walk you a bit more thoroughly through my usual process of breaking down the problem we’re trying to solve, moving into pseudo-code, and then my usual manual walk-through. So first, the problem…

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)

"KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints:

1 <= s.length <= 100

s contains only digits and may contain leading zero(s).

There’s a decent amount being asked in this problem, so let’s pull out issues we need to keep in mind while determining our course of action.

• if the first digit of the string is 0 return 0, because nothing can start with a leading zero
• if there are two zeros in a row, the return should be zero because it will be un-decodable
• any single character between 1 and 9 will be a valid way to decode, so the only invalid singles are 0s
• if a character is a zero, the only valid doubles are 10 or 20
• doubles are only valid if 10 <= double <= 26

Those are some good parameters to start with, let’s keep moving. I’ll go through my thought process and the decisions that went into solving this.

// create an array to keep track of the number of possible solutions as we move through the original string

// new array, set length of s.length + 1, pre-filled with zeros, so as we check if single and double are valid we can add up the decode options

// we already know that anything but zero is a valid single, so we can pre-fill index 0 and 1 to equal 1

So we can go ahead and get the above code started. First we’ll create our pre-filled array of 0s. Then take care of the leading zero issue — we do this here at the top so that we don’t have to account for it inside the loop, because we don’t want to waste time moving into the loop at all. After that we can set howManyDecodes[0] = 1 and howManyDecodes[1] = 1. And of course we can go ahead and write out our return, since I’m planning on counting and tracking possible decode options in my array, we’ll want to return the last one.

At this point I have an idea of how I want to loop through our string. With more harder loops, tracking and comparing multiple things, I like to do a manual walk through just to make sure that what I’m imagining in my mind makes sense on “paper”. The examples given in the problem were too short and lacking interior zeros for a walk through to really solidify my plan, so I walked through with my own example. Let’s take a walk!

Manual step-by-step walkthrough of my future for loop.

Doing this walk-through ensures that the logic I plan to use is not only accurate but more importantly, that it makes sense. It also helps me check that I am accounting for potential edge cases within a loop. As you can see in my test number I made sure to include valid and invalid numbers to ensure that I was adding the number of potential decodes accurately.

And now, finally, after some pseudo-code and my logic walk-through, I should be ready to write my for loop.

That’s it. Somehow, it’s that simple. Crazy, right? There are so many ways one could go about determining the validity of single and double digits within the given parameters, and this is just the way I chose to do it. This is the way that made sense to me, the way my brain works.

When I start considering more complex problems like this I begin by looking for patterns. Trying to find often mathematical solutions to the question. Occasionally the pattern jumps out and it’s off to the races, and other times the pattern doesn’t appear until I’m halfway down the wrong path or even just the longer more windy path. Either way finding a pattern and investigating it has yet to serve me wrong. If you look at algorithms and feel lost, take a breath and look for patterns, just like the magic eyes of old, the more you practice finding the pattern, the easier they’ll start jumping out at you.

Watch out for that shark!