LeetCode 91. Decode Ways

 Today, I continued with exploring dynamic programming problems. So, I came across this problem Decode Ways - LeetCode. 

Problem:

This problem description says that there is an inherent mapping in between Alphabets and numbers. 

We would be provided with string of numbers, and we have to count unique number of ways to decode it. For example, if given string of numbers is "11106" then it can be broken down into two groupings:

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 like this we need to return number of ways for breaking down this string into valid alphabet.

Solution and thought Process:

We can break down this problem recursively. I do generally follow HIB (Hypothesis Induction Base condition) based approach for solving any kind of recursion problem.

Let's focus first on Hypothesis and Induction step: any valid string s [0, n] can be broken down into two substrings i.e., s [0, n] = s [0, i] + s [i+1, n] where i can be {1,2} as max allowed string size is 2 (Z:26).

Then, let's talk about base condition, from the definition of base condition it is the smallest possible positive or negative case. In this case I am taking case of empty string this means we can safely terminate the processing of the string as it cannot be processed further.

Here is my code snippet for same, showing base condition and hypothesis steps in the given boxes:

Here the caller method.