leetcode — decode-ways
2024-08-25 17:15:46
/**
* Source : https://oj.leetcode.com/problems/decode-ways/
*
*
* 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.
*/
public class DecodeWays {
/**
* 找出有多少种解码方式
*
* 使用递归，但是复杂度较高，可以考虑使用DP
*
* 当XY > 26的时候 dp[i+1] = dp[i]
* XY <= 26 的时候 dp[i+1] = dp[i] + dp[i-1]
*
*
* 临界条件：
* X = 0,dp[i+1] = dp[i]
* Y = 0,dp[i+1] = dp[i-1]
*
* @param digits
*/
public int findWays (String digits) {
if (digits == null || digits.length() == 0 || digits.charAt(0) < '1' || digits.charAt(0) > '9') {
return 0;
}
int[] dp = new int[digits.length() + 1];
dp[0] = dp[1] = 1;
for (int i = 1; i < digits.length(); i++) {
if (digits.charAt(i) > '9' || digits.charAt(i) < '1') {
return 0;
}
int x = digits.charAt(i-1) - '0';
int y = digits.charAt(i) - '0';
int xy = x * 10 + y;
if (xy > 9 && xy <= 26) {
dp[i+1] = dp[i] + dp[i-1];
} else if (y != 0) {
dp[i+1] = dp[i];
}
if (dp[i+1] == 0) {
return 0;
}
}
return dp[dp.length-1];
}
public static void main(String[] args) {
DecodeWays decodeWays = new DecodeWays();
System.out.println(decodeWays.findWays(""));
System.out.println(decodeWays.findWays("1"));
System.out.println(decodeWays.findWays("12"));
System.out.println(decodeWays.findWays("32"));
System.out.println(decodeWays.findWays("10"));
System.out.println(decodeWays.findWays("00"));
System.out.println(decodeWays.findWays("09"));
}
}
最新文章
- postman发送带cookie的http请求
- Android编码规范02
- SQL JOIN\SQL INNER JOIN 关键字\SQL LEFT JOIN 关键字\SQL RIGHT JOIN 关键字\SQL FULL JOIN 关键字
- 10款html5开发工具，实用+好用
- Newtonsoft.Json 把对象转换成json字符串
- Linux下Redis服务器安装配置
- Hexo搭建Github静态博客
- 英文 数字 不换行 撑破div容器
- bootstrap轮播组件,大屏幕图片居中效果
- 自定义jquery表格插件
- mxnet框架样本，使用C++接口
- happyChat开发系列：使用websocket.io实现双向通信的乐聊大前端开发
- innobackupex 远程备份
- SQL约束（主键约束、外键约束、自动递增、不允许空值、值唯一、值默认、值限制范围）
- 洛谷P1038神经网络题解
- 5句话搞定ES5作用域
- Bootstrap学习笔记-栅格系统
- [转]NSIS：安装、卸载时检查程序是否正在运行
- springMvc的执行流程(源码分析)
- Form,选择并转移导航菜单