LeetCode（91）：解码方法 Decode Ways（Java）

2019.6.12 #程序员笔试必备# LeetCode 从零单刷个人笔记整理（持续更新）

和之前刷的零钱兑换很像，底层是个01背包问题：物品有两种规格，要么一个数字，要么满足要求的两个数字。运用标准的动态规划即可：

建立动态规划数组dp，dp[i]用于记录字符串至第i-1位前的解码方法的总数。依次扫描数字，当前数字不为0时，dp[i]+=dp[i-1]表示当前组合数量包括前一位数字前的组合总数；当前数字与前一位组合的数字处于10-26时，dp[i]+=dp[i-2]表示当前组合数量包括前两位数字前的组合总数。最后只需要返回dp[s.length()]即可。

有个tip是当两位数算得0时，说明字符串出现连续两个0，此时可以直接返回0.因为"00"所在的字符串不存在解码方式。

---

传送门：解码方法

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.

一条包含字母 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) 。

---

/**
 *
 * 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.
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
 *
 */

public class DecodeWays {
    //动态规划
    public int numDecodings(String s) {

        //dp[i]用于记录字符串至第i-1位前的解码方法的总数
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;

        for(int i = 1; i < s.length() + 1; i++){
            //当前数字不为0时，dp[i] += dp[i - 1]表示当前组合数量包括前一位数字前的组合总数
            char c = s.charAt(i - 1);
            if(c != '0'){
                dp[i] += dp[i - 1];
            }
            //当前数字与前一位组合的数字处于10-26时，dp[i] += dp[i - 2]表示当前组合数量包括前两位数字前的组合总数
            if(i > 1){
                int num = (s.charAt(i - 2) - '0') * 10 + (c - '0');
                //提前剪枝：连续两个0没有对应解码方式
                if(num == 0){
                    return 0;
                }
                if(num > 9 && num < 27){
                    dp[i] += dp[i - 2];
                }
            }
        }

        return s.length() == 0 ? 0 : dp[s.length()];
    }
}

---

#Coding一小时，Copying一秒钟。留个言点个赞呗，谢谢你#