20200731-91-解码方法.md

每天一道leetCode

信息卡片

• 时间：2020-07-31
• 题目链接：https://leetcode-cn.com/problems/decode-ways
• tag：动态规划

### 题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

参考答案

动态规划

对于由给定字符串转换成的字符数组nums，dp[i]表示，第i项为结尾的解码方法数。分情况讨论，推到转移方程：

• 如果nums[i] = '0'，需要判断num[i - 1] 是否等于'1'或者'2'，如果不成立，则无法解码直接返回0即可；如果成立，dp[i] = dp[i - 2]，这是因为如果是10或者20则编码方式是唯一的，不会增加数量
• 如果nums[i - 1] = '1' 或者nums[i - 1] = '2' 且 nums[i] 在'1'-'6'之间，那么dp[i] = dp[i - 1] + dp[i - 2]，这是因为如果num[i]和nums[i - 1]分开解码，则为dp[i - 1]，合并解码则为dp[i - 2]

class Solution {
    public int numDecodings(String s) {
        char[] nums = s.toCharArray();
        if (nums[0] == '0') {return 0;}
        int pre = 1, cur = 1;
        for (int i = 1; i < nums.length; i++) {
            int temp = cur;
            if(nums[i] == '0') {
                if (nums[i - 1] == '1' || nums[i - 1] == '2') {
                    cur = pre;
                } else {
                    return 0;
                }
            } else if (nums[i - 1] == '1' || (nums[i - 1] == '2' && nums[i] <= '6' && nums[i] >= '0')) {
                cur = pre + cur;
            }
            pre = temp;
        }
        return cur;
    }
}