[leetcode] 91. Decode Ways

[leetcode] 91. Decode Ways

Description

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: 2Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"Output: 3Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

分析

题目的意思是：题目给出了一些解码的规则，要求按照给定的规则解码，求解码方式有多少种。

这道题可以用dp来解决，跟爬梯子问题很相似，只是加了一些限制条件，把这些条件加入到dp中就行了，怎么加就看代码了。dp[i] 表示i的字符的合法编码数量，取决于当前字符。对每个数组的数判断如果为非0，则赋上一个dp值，此时相当如加上了dp[i - 1], 然后看数组前一位是否存在，如果存在且满足前一位不是0，且和当前为一起组成的两位数不大于26，则当前dp值加上dp[i - 2]。从整体来看，跟斐波那契数组的递推式一样，

代码

class Solution {public: int numDecodings(string s) { if(s.length()==0||s[0]=='0'){ return 0; } vector dp(s.length()+1,0); int n=s.length()+1; dp[0]=1; // 当有0个字符时候的编码个数，当有连续两个字符能编码时f[i] = f[i-2]，保证f[0]有值 dp[1]=1; // 字符串长度为1时的编码个数 for(int i=2;i='1'&&s[i-1]<='9'){ dp[i]+=dp[i-1]; } if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]>='0'&&s[i-1]<='6')){ dp[i]+=dp[i-2]; } } return dp[s.length()]; }};

代码二 (python)

class Solution: def numDecodings(self, s: str) -> int: if(s[0]=='0'): return 0 n=len(s) dp=[0]*(n+1) for i in range(n+1): if(i==0 or i==1): dp[i]=1 continue if(s[i-1]!='0'): dp[i]+=dp[i-1] if(i>1 and (s[i-2]=='1' or (s[i-2]=='2' and s[i-1]<='6'))): dp[i]+=dp[i-2] return dp[n]

参考文献

​​[LeetCode] Decode Ways 解码方法​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。