javascript - 可能的组合和转换成字母表的算法 - Javascript(由 Facebook 询问)

Question

我正在研究下一次面试的算法，我发现了这个问题。

Facebook 问的

问题来了。

---

给定映射 a = 1，b = 2，... z = 26，以及一条编码消息，计算它可以被解码的方式的数量。

例如，消息“111”会给出 3，因为它可以被解码为“aaa”、“ka”和“ak”。

---

我想我可以处理映射和转换为字母部分。但是组合对我来说并不容易。

想出下面这段代码我花了好几个小时。

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);

我只有这个。

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

查看重复项。我想我现在可以除以 2 并得到我想要的答案。这仍然不是一个好的答案。

你能把它变成更好的代码吗？

谢谢

---

上面的代码几乎都是出自这个 link

Answer 1

在这种情况下，我们不需要实际创建组合来计算它们。我们可以使用 dynamic programming .

令 f(i) 表示解码字符串 S 中消息的有效方式的数量，直至并包括索引 i< 处的字符(从零开始)。然后:

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)

例子:

S = "123"

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

这个过程的复杂度是O(n) 时间和O(1) 空间。