|
【题目描述】
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
有一个消息包含A-Z通过以下规则编码
'A' -> 1
'B' -> 2
...
'Z' -> 26
现在给你一个加密过后的消息,问有几种解码的方式
【题目链接】
www.lintcode.com/en/problem/decode-ways/
【题目解析】
此题可使用动态规划。
设置动态数组dp[n+1]。dp表示从1~i的decode ways的个数。
当给的code只有一位数时,判断是不是valid(A~Z),是的话就dp[1] = 1 不是的话就是dp[1] = 0
因为像给的例子12可以有两种可能的解析方法,所以计算dp的时候要判断两种可能性,再累加。
【参考答案】
www.jiuzhang.com/soluti**/decode-ways/
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
|
|