网站建设服务费开票,成都旅游攻略四天三夜,企业网站建设示范平台,工程平台公司做什么的一条包含字母 A-Z 的消息通过以下映射进行了 编码 #xff1a;
1 - A 2 - B ... 25 - Y 26 - Z
然而#xff0c;在 解码 已编码的消息时#xff0c;你意识到有许多不同的方式来解码#xff0c;因为有些…一条包含字母 A-Z 的消息通过以下映射进行了 编码
1 - A 2 - B ... 25 - Y 26 - Z
然而在 解码 已编码的消息时你意识到有许多不同的方式来解码因为有些编码被包含在其它编码当中2 和 5 与 25。
例如11106 可以映射为
AAJF 将消息分组为 (1, 1, 10, 6)KJF 将消息分组为 (11, 10, 6)消息不能分组为 (1, 11, 06) 因为 06 不是一个合法编码只有 6 是合法的。
注意可能存在无法解码的字符串。
给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串返回 0。
题目数据保证答案肯定是一个 32 位 的整数。 示例 1
输入s 12
输出2
解释它可以解码为 AB1 2或者 L12。示例 2
输入s 226
输出3
解释它可以解码为 BZ (2 26), VF (22 6), 或者 BBF (2 2 6) 。示例 3
输入s 06
输出0
解释06 无法映射到 F 因为存在前导零6 和 06 并不等价。 这道题我没有思路官方思路如下
动态规划
用一个f[i]数组表示以下标i结尾的解码方法数量
如果第一个就是0那return 0即可
否则初始化f[0]1表示有一种解码方法
然后遍历如果自己本身不为0那f[i]f[i-1]可以累加
如果自己为0且前一个数不为0那判断自己和前一个数组合起来如果值在10~26之内就合法
f[i]f[i-2](如果i-2存在的话
class Solution {public int numDecodings(String s) {int ns.length();int f[]new int[n];if(s.charAt(0)0){return 0;}f[0]1;for(int i1;in;i){if(s.charAt(i)!0){f[i]f[i-1];}if(i-20(s.charAt(i-1)-0)*10(s.charAt(i)-0)26s.charAt(i-1)!0){f[i]f[i-2];}if(i-20(s.charAt(i-1)-0)*10(s.charAt(i)-0)26){f[i]1;}}return f[n-1];}
}
