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