(Java) LeetCode 91. Decode Ways —— 解码方法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了(Java) LeetCode 91. Decode Ways —— 解码方法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2611字，纯文字阅读大概需要4分钟。
内容图文
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A‘ -> 1 ‘B‘ -> 2 ... ‘Z‘ -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
这个题想了好久，觉得真的是比较难想，好多case一遍一遍测试才通过。试着总结一下思路吧。
首先，假如我们分析到了中间，比较通用的情况。
现在在已有字符串的基础上，新来一位字符，就要开始分情况。如果来的是‘0‘，就只有唯一的组成情况，就是和前面的一个数字组成编码，且前面的这个数字还必须是‘1‘或‘2‘，否则就是无效的编码。所以如果来的是‘0‘，相当于要么和前面的数字组合，要么就无效。如果用动态规划的思想，那就先写上伪代码：
if (s[i] == ‘0‘) {
if (s[i-1] == ‘1‘ || ‘2‘)
dp[i] = dp[i-2];
else
return 0;
}
这里为什么是dp[i] = dp[i-2]呢？因为‘0‘只能作为和前面的一位字符组合存在，所以前面的字符出现的时候相当于并没有出现，因为它要等着后面的‘0‘来和它组合，所以编码种类和dp[i-2]一样多。
接下来看如果来的是‘1‘~‘9‘，不仅自己要再细分情况，也要再考虑前面一位的情况。如果前面一位是‘1‘，或前一位是‘2‘且这一位是‘1‘~‘6‘，那么可以产生新的编码，因为它既可以独立存在成一个字母，又可以和前面的数字组合形成一个字母。作为独立存在的情况相当于就是取dp[i-1]，因为添加一位独立存在的字符并没有增加任何可能性，所以保持和前状态一样；作为组合存在的情况同上，还要再往前想一位。因为如果组合存在的话，前面的一位其实也是和后面的一位作为组合存在而不是独立存在，即当dp[i-1]那位字符来的时候，装作它没来，因为它要等着和后面的字符结合，所以编码种类和dp[i-2]是一样多的。所以最后dp[i] = dp[i-1] + dp[i-2]。
如果前面一位字符不是‘1‘或者‘2‘，那么新来的字符位只能作为独立存在，无法结合。所以并没有产生新的编码可能，即dp[i] = dp[i-1]。
总结起来伪代码如下：
if (s[i-1] == ‘1‘ || (s[i-1] == ‘2‘ && ‘1‘ <= s[i] <= ‘6‘)) dp[i] = dp[i-1] + dp[i-2]; else dp[i] = dp[i-1];
这样所有的情况就分析完了。现在看为了解决通用情况需要些什么，很明显从上面来看，需要知道每一位字符前两位，即dp[0]和dp[1]要首先知道。dp[0]很简单，如果不是‘0‘那就是1，是‘0‘就直接返回0了，第一位是‘0‘无法解码。dp[1]也并不复杂，其实和通用情况一样，如果第二位是‘0‘，dp[1]就是1或return 0，取决于能否和前面结合，即第一位是否是‘1‘或‘2‘；如果第一位是‘1‘，或第一位是‘2‘且第二位是‘1‘~‘6‘，那dp[1]就是2，因为可以结合或独立存在。其他情况就都是1了，因为只能独立存在，不增加解码可能性。
写完了思路发现这道题就写完了，把思路实现即为代码。应该是有很多可以优化的地方，或者是思绪上，或者是代码上，留作以后复习的时候优化吧。现在这么写思路特别清楚，很容易理解，姑且先这样吧！
Java
class
Solution {
public
int
numDecodings(String s) {
if (s == "") return 0;
char[] digit = s.toCharArray();
int[] dp = newint[digit.length];
//get dp[0]
dp[0] = digit[0] == ‘0‘ ? 0 : 1;
if (dp[0] == 0 || digit.length == 1) return dp[0];
//get dp[1]
dp[1] = 1;
if (digit[1] == ‘0‘) {
if (digit[0] >= ‘3‘)
return 0;
}
elseif (digit[0] == ‘1‘ || (digit[0] == ‘2‘ && ‘1‘ <= digit[1] && digit[1] <= ‘6‘))
dp[1] = 2;
//get dp[i]for (int i = 2; i < digit.length; i++) {
if (digit[i] == ‘0‘) {
if (digit[i-1] == ‘1‘ || digit[i-1] == ‘2‘)
dp[i] = dp[i-2];
elsereturn 0;
}
elseif (digit[i-1] == ‘1‘ || (digit[i-1] == ‘2‘ && ‘1‘ <= digit[i] && digit[i] <= ‘6‘))
dp[i] = dp[i-1] + dp[i-2];
else dp[i] = dp[i-1];
}
return dp[digit.length-1];
}
}
原文：https://www.cnblogs.com/tengdai/p/9245714.html
内容总结
以上是互联网集市为您收集整理的(Java) LeetCode 91. Decode Ways —— 解码方法全部内容，希望文章能够帮你解决(Java) LeetCode 91. Decode Ways —— 解码方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。