我正在研究下一次面试的算法,我发现了这个问题。
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
最佳答案
在这种情况下,我们不需要实际创建组合来对它们进行计数。我们可以使用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)
空间。
关于javascript - 可能的组合并转换为字母算法 - Javascript(Facebook 询问),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48180388/