Possible combinations and convert into alphabet algorithm - Javascript (asked by Facebook)

Question

I am studying algorithm for my next interview, And i found this problem.

Which was asked by Facebook

Here's the problem.

---

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa, 'ka', and 'ak'.

---

I think I can handle with the mapping and converting to alphabet part. But making combinations is not easy for me.

Consider that it took me several hours to come up with this code below.

function combinations(str) {
var fn = function(active, rest, a) {

    // if nothing, just return
    if (!active && !rest)
        return;


    // there is nothing left in rest add active to A
    if (rest.length == 0) {
        a.push(active);
    } else {

        // append first number of rest to the end of the active item
        // [1] + 1 => 111
        // [1,2] + [3,4] = [1,2,3] + [4]
        if (rest.length > 0){
            fn(active.concat(rest[0]), rest.slice(1), a);
        }else {}


        // join 

        fn((active+rest[0]).split(","), rest.slice(1), a);
    }
    return a;
  }
  return fn([], str, []);
}

// run it
combinations(1,2,3);

I only got this.

[ [ 1, 2, 3 ],
[ '1', '23' ],
[ '12', 3 ],
[ '123' ],
[ '1', 2, 3 ],
[ '1', '23' ],
[ '12', 3 ],
[ '123' ] ]

See the duplicate item. I think I can now divide by 2 and get answers I want. Still it is not really a good answer.

Can you make it into better code?

Thank you

---

The code above is almost from this link

Answer 1

In this case, we don't need to actually create the combinations in order to count them. We can use dynamic programming.

Let f(i) represent the number of valid ways to decode the message in string, S, up to and including the character at index i (zero-based). Then:

f(0)  = 1
f(i)  =
   if S[i] > 6 or S[i-1] > 2:
     // Nothing changes, we just
     // added a letter
     f(i-1)

   else:
     // All the ways to decode
     // up to (i-1) plus all the
     // ways to decode up to (i-2)
     // (let f(-1) equal 1)
     f(i-1) + f(i-2)

Example:

S = "123"

f(0) = 1
f(1) = f(0) + f(-1) = 2
f(2) = f(1) + f(0) = 3

The complexity of this process is O(n) time and O(1) space.