题目如下:
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: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
A-Z分别编码成1-26,给定一串编码后的数字串,问我们有多少种合法的解码方法。
这道题可以用动态规划的方法解决,解题思路和LeetCode-70爬楼梯问题类似定义状态空间dp[i]表示从第1个到第i个数字的解码方法,求解状态空间时有以下两种情况:
1.第i个字符单独解码,则dp[i] == dp[i-1];
2.第i个字符和第i-1个字符一同解码,则dp[i] == dp[i-2]。
综合考虑以上两种情况以及边界条件,代码如下:
class Solution { public int numDecodings(String s) { if (s.isEmpty() || s.charAt(0) == '0') { return 0; } int[] dp = new int[s.length() + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= s.length(); i++) { char one = s.charAt(i - 1); int two = Integer.parseInt(s.substring(i - 2, i)); if (one != '0') { dp[i] += dp[i - 1]; } else { if (s.charAt(i - 2) > '2' || s.charAt(i - 2) == '0') { return 0; } } if (two >= 10 && two <= 26) { dp[i] += dp[i - 2]; } } return dp[s.length()]; } }
- 本文固定链接: https://weiguangli.com/archives/447
- 转载请注明: lwg0452 于 Weiguang的博客 发表
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!