【LeetCode】解码方法 Java 题解
题目描述
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
'A' -> 1'B' -> 2...'Z' -> 26 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:
"AAJF" ,将消息分组为 (1 1 10 6)"KJF" ,将消息分组为 (11 10 6)注意,消息不能分组为 (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
复制代码
代码
复制代码
总结
这个题目是求解个数问题,动态规划是比较好的解决方案。
状态转移方程,根据题目提示,考虑单个字符的解码方式,两个字符的解码方式,分为 2 种情况讨论。
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/32751bf46992bc01df666be67】。文章转载请联系作者。
评论