Leetcode91.Decode Ways解码方法
2024-09-06 02:40:50
一条包含字母 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) 。
class Solution {
public:
int numDecodings(string s)
{
int len = s.size();
if(len == 1)
return s[0] == '0'? 0 : 1;
if(s[0] == '0')
return 0;
vector<int> dp(len, 0);
dp[0] = 1;
int x = (s[0] - '0') * 10 + s[1] - '0';
if(s[1] == '0' && s[0] <= '2' && s[0] >= '1')
dp[1] = 1;
else if(s[1] == '0' && s[0] > '2')
return 0;
else if(x <= 26 && x >= 1)
{
dp[1] = 2;
}
else
dp[1] = 1;
for(int i = 2; i < len; i++)
{
int x = (s[i - 1] - '0') * 10 + s[i] - '0';
if(x == 0)
return 0;
else if(s[i - 1] == '0')
{
dp[i] = dp[i - 1];
}
else if(s[i] == '0' && s[i - 1] <= '2' && s[i - 1] >= '1')
{
dp[i] = dp[i - 2];
}
else if(s[i] == '0' && s[i - 1] > '2')
{
return 0;
}
else if(x <= 26 && x >= 1)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
else if(x > 26)
dp[i] = dp[i - 1];
}
return dp[len - 1];
}
};
最新文章
- [Vuejs] 关于vue-router里面的subRoutes
- Liferay 6.2 改造系列之二十四:修改liferay密码的加密方式
- cocos2dx 3.x(动态改变精灵的背景图片)
- dubbo源码之三——dubbo重构
- Elementary os的安装
- 版权控制之zend guard 6.0使用教程
- ssh连接超时问题解决方案
- EclipsePHP Studio 常用设置笔记
- 字符设备驱动: register_chrdev和register_chrdev_region
- PowerShell 批量导入/导出Active Directory
- 【iOS发展-81】setNeedsDisplay刷新显卡,并CADisplayLink它用来模拟计时器效果
- 安卓自定义类似TabHost的导航栏
- 前端要革命?看我在js里写SQL
- 004_浅析Python的GIL和线程安全
- js性能提高篇
- 输入两棵二叉树A,B,判断B是不是A的子结构(c++实现)
- Apache 性能配置优化
- HDU 6040 stl
- JDBC的简单操作
- MySQL-高并发优化