【leetcode刷题笔记】Decode Ways
2024-08-26 02:56:12
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
题解:DP问题。
对于s中位置i(s[i] != '0')上的字符,有两种可能:
- 直接把i译码成对应的字母,那么此时有dp[i-1]中方法;
- 如果i和i-1上的字符可以共同组成一个字母(s(i-1,i)在[10,26]范围中),那么又有dp[i-2]种译码方法,所以此时dp[i] = dp[i-1]+dp[i-2];
代码如下:
public class Solution {
private boolean isValidNum(String s,int i){
if(i <= 0)
return false;
int first = s.charAt(i-1)-'0';
int second = s.charAt(i)-'0';
int num = first*10 + second;
if(num >= 10 && num <= 26)
return true;
return false;
}
public int numDecodings(String s) {
if(s==null || s.length() == 0)
return 0;
int length = s.length();
int[] dp = new int[length+1]; dp[0] = 1;
dp[1] = s.charAt(0) == '0'?0:1; for(int i=2;i<=length;i++){
if(s.charAt(i-1) != '0')
dp[i]=dp[i-1]; if(isValidNum(s, i-1))
dp[i] += dp[i-2];
}
return dp[length];
}
}
最新文章
- 浅谈WEB前后端分离
- SQL查询树形结构的所有子节点
- APT 常用功能
- 解决IE不支持position:fixed问题
- ado.dataset
- iOS 定时器Timer常见问题
- Junit4_单元测试
- 乱译文档--开始使用Musca
- c#程序为PDF文件填写表单内容
- spring jdbc 笔记3
- express框架+jade+bootstrap+mysql开发用户注册登录项目
- 网页 CSS样式表
- The first to Python
- HTML语义化的理解
- js与jq基础记录
- php二维数组根据某个字段去重
- Vue-admin工作整理(四):路由组件传参
- Eureka多机高可用
- NPOI导出Excel2007板
- 【LeetCode】128. 最长连续序列