有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，给出有多少种可能的译码结果。
[编程题]解码
跳楼梯Plus版
我们考虑在下标为k处的情况：第k处的译码方案数量应该是k - 1处的译码数量 + k - 2处的译码数量（k - 1位对应只译1位的情况，即a-i，k - 2位对应只译2位的情况，即j-z）。用代码来表达就是dp[k] = dp[k - 1] + dp[k - 2]
但是，会出现以下特殊情况：
1. 第k - 1、k位均为0，即字符串中存在'00'的情况。这个时候怎么译都不行的（哪怕前面的0跟了k - 2位一起译，还会剩下一个0没法翻译），答案直接返回0就行。
2. 第k - 1位不为0（为1或2），但第k位为0。这个时候第k位必须要跟第k - 1位一起译，因此解决方案数只有第k - 1位的解决方案，即dp[k] = dp[k - 1]。
3. 第k - 1位为0，但第k位不为0。这个时候只有一种译码方法（就是a-i选一个，k - 1位的0要跟k - 2位一起译），因此此解决方案数只有第k - 1位的解决方案，即dp[k] = dp[k - 1]。
4. 第k - 1、k位合起来的数超过26了，这个时候是没有字母对应的，也译不了，因此解决方案数只有第k - 1位的解决方案，即dp[k] = dp[k - 1]。
综上所述，应有：
如果输入字符串s中有'00'，返回0
如果int(s[k - 2: k] (两端均取)) <= 10 或 == 20 或 > 26: dp[k] = dp[k - 1]
否则dp[k] = dp[k - 1] + dp[k - 2]。
跟跳楼梯类似，我们可以用一个长数组来记录每一步的结果。但是这个状态转移方程只与前两步的结果有关，可以只用一个长度为2的数组迭代，即把空间复杂度降为O(1)。
AC代码：
class MainActivity: def main(self): # Read the data s = input() if '00' in s: print(0) return # Initialization results = [1, 0 if s[0] == '0' else 1] # Traverse for ptr in range(1, len(s)): part = int(s[ptr - 1: ptr + 1]) if part <= 10&nbs***bsp;part == 20&nbs***bsp;part > 26: results.append(results[-1]) else: results.append(sum(results)) results.pop(0) print(results[-1]) if __name__ == '__main__': M = MainActivity() M.main()
发表于 2024-08-26 12:16:35
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-19 22:21:32 -
2022-08-27 19:03:19
-
2022-08-27 15:15:05 -
2022-08-26 11:42:17
-
2022-08-11 23:11:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
