Decode

Problem:

You are given a mapping of alphabets to a particular code. The code is in 1s and 0s. For example

a - 1101
b - 01
c - 1000

The minimum size of this code is 1 and the maximum is 4.

You are now given a string to encode using the mapping above. For example abc is the input string. The encoded form should be 1101011000. This form can however be decoded to a variety of output strings. With the mapping in place, perhaps this encoded word can be interpreted as xrt instead of abc where x=110 r=1011 and t=000.

Given these requirements how do you write a function that returns the maximum possible number of strings that can be interpreted from the encoded string ? The output string must be of the same length as the input string.

Test case:

Let us say 1101011000 can be decoded to abc , xrt and repp. The program should output '2' since there are 2, 3 letter strings that can be found from the encoded string. Any string whose length is greater or lesser than the original string is not counted.

Hint: -> You can recursively backtrace when you dont have a match.

Hint: -> Look at the test cases carefully when programming the solution. Brute force will work.

Visualization of the solution:



You can traverse through each solution by branching from one alphabet to the next.





What changes must be made to the program in case duplicate letters are not allowed ?

How can the solution be optimized and when does the program know which branch to stop looking in ?