v****e
发帖数: 145 | 1 Given a mapping between numbers and alphabets . Find the number of ways to
decode a sequence of numbers
eg: a - 21 b - 2 c - 54 d - 5 e -4 f-1
2154
1) ac
2) ade
3) bfc
4) bfde
4 ways to decode
http://stackoverflow.com/questions/15586047/given-an-encoded-me
SF上有人用DP解答，并用如下递推公式：Way[n] = Way[n-1] + Way[n-2] 请问这个公
式是如何得出的。如果在上例中有三位数字对应的字母，是不是可以演变成Way[n] =
Way[n-1] + Way[n-2] + Way[n-3]? 这是为什么呢？ |
x****g
发帖数: 39 | 2 这个参见 leetcode climbing stairs
那个答案不对啊，如果有一个substr 无法翻译就需要改动了，不过也好改。
【在 v****e 的大作中提到】
: Given a mapping between numbers and alphabets . Find the number of ways to
: decode a sequence of numbers
: eg: a - 21 b - 2 c - 54 d - 5 e -4 f-1
: 2154
: 1) ac
: 2) ade
: 3) bfc
: 4) bfde
: 4 ways to decode
: http://stackoverflow.com/questions/15586047/given-an-encoded-me
|
v****e
发帖数: 145 | 3 我也觉得有点问题。不过只需要把每一项乘以一个bool值再相加。
bool值代表着是否可以被翻译。
【在 x****g 的大作中提到】
: 这个参见 leetcode climbing stairs
: 那个答案不对啊，如果有一个substr 无法翻译就需要改动了，不过也好改。
|
f********y
发帖数: 156 | 4 这个类似wordbreak, 用dp做
用way[n-1]前，要查表看最后一位数字是否对应一个字符
同样，用way[n-2]前，要看最后两位是否对应某个字符 |
