题目如下:
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()];
- }
- }