题目描述

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).

算法1

(动态规划)

时间复杂度 O(n)

步骤1: 确定状态
最后一个元素，一定是从一位或者两位数字组合而来1～26之间，所以最后一个数字有两个情况。
1.最后一个元素是1～9之间的字母。例如50种解密方式。

2.最后一个元素是10~26之间的字母。例如100种解密方式。那么最后两种情况加起来有50+100=150种。
状态：dp[i]：以 s[i] 结尾的前缀子串有多少种解码方法。

步骤2: 确定状态转移方程
dp[i] = dp[i-1] 【s[i]是一位数字】 + dp[i-2] 【s[i-1]是一位数字】

步骤3. 考虑边界和初始状态
dp[0] = 1;

步骤4. 计算顺序,dp[0],dp[1]…dp[n-1]一步步计算

Java代码

class Solution {

    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }

        int n = s.length();
        //dp[i]表示到字符串s下标i处时最多有几种解码方式
        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            char ch = s.charAt(i);
            int num = 10 * (s.charAt(i - 1) - '0') + (ch- '0');
            //单独处理i==1
            if (i == 1) {
                // 1-9
                if (s.charAt(i) != '0') {
                    dp[i] = dp[i - 1];
                }
                // 10-26
                if (num >= 10 && num <= 26) {
                    dp[i]++;
                }
                continue;
            }

            // case 1: 最后一个元素是1～9之间的字母
            if (ch != '0') {
                dp[i] = dp[i - 1];
            }

            // case 2: 最后一个元素是10~26之间的字母
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i - 2];
            }

        }

        return dp[n - 1];
    }
}