首页 > 试题广场 >

数字字符转化为字母组合的种数

[编程题]数字字符转化为字母组合的种数
  • 热度指数：3207 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串str，str全部由数字字符组成，如果str中的某一个或者相邻两个字符组成的子串值在1~26之间，则这个子串可以转换为一个字母。规定‘1’转换为“A”，“2”转换为“B”......"26"转化为“Z“。请求出str有多少种不同的转换结果，由于答案可能会比较大，所以请输出对取模后的答案。

输入描述:
输出一行仅有’0‘~’9‘组成的字符串，代表str 。


输出描述:
输出一个整数，代表你所求出的取模后答案。
示例1

输入

1111

输出

5

说明

能转换出来的结果有：“AAAAA”，“LAA”，“ALA”，“AAL”，“LL”。
示例2

输入

01

输出

0

说明

“0”没有对应的字符，而“01”是不可转换的。
示例3

输入

18

输出

2

备注:
时间复杂度,空间复杂度
算法知识视频讲解
开通博客
头像 星晨
发表于 2020-11-18 23:10:36
要求多少种不同的转换结果每个位置我们都应该去两种选择 当前位 当前位和下一位 但是要求 O（n） 和 O（1）就绝不可能是动态规划了我们可先不考虑空间复杂度分解一下问题假设 dp[i] 标示前i个子串转化为字母组合的方案则 如果第i个字母可以单独转换，则 dp[i] = dp[i]-1 如果第 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
上传者：小小
难度：
9条回答 5031浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数字字符转化为字母组合的种数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号