欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode(91):解码方法 Decode Ways(Java)

程序员文章站 2022-07-05 14:22:19
...

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一秒钟。留个言点个赞呗,谢谢你#