首页 > 试题广场 >

把数字翻译成字符串

[编程题]把数字翻译成字符串
  • 热度指数：151641 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0 < n \leq 90
进阶：空间复杂度 ，时间复杂度
示例1

输入

"12"

输出

2

说明

2种可能的译码结果（”ab” 或”l”）
示例2

输入

"31717126241541717"

输出

192

说明

192种可能的译码结果
算法知识视频讲解
添加回答
Python
SunnyKris快点拿offer头像 SunnyKris快点拿offer
求问哪位大神知道为什么我这样写过不了最后一个例子呀！ 
class Solution:
    def solve(self , nums ):
        # write code here
        if not nums:
            return
        if len(nums) == 1:
            if nums == '0':
                return 0
            return 1
        n = len(nums)
        x, y = 1, 1
        for i in range(0, n-1):
            if int(nums[i:i+2]) == 0:
                return 0
            elif 11 <= int(nums[i:i+2]) <= 26:
                res = x + y
            else:
                res = y
            x = y
            y = res
        return res


发表于 2021-12-14 06:40:50 回复(0)
Python
奋斗的习习张头像 奋斗的习习张 
#
# 解码
# @param nums string字符串 数字串
# @return int整型
# 动态规划，dp[0]和dp[1]的构造场景比较多
class Solution:
    def solve(self, nums):
        # write code here
        if not nums&nbs***bsp;nums[0] == "0":
            return 0
        dp = [1]
        if len(nums) > 1:
            if nums[1] == "0":
                if int(nums[0]) > 2:
                    return 0
                dp.append(1)
            elif int(nums[0]) < 2&nbs***bsp;(int(nums[0]) == 2 and int(nums[1]) <= 6):
                dp.append(2)
            else:
                dp.append(1)
        for i in range(2, len(nums)):
            if nums[i] == "0":
                if int(nums[i-1]) > 2&nbs***bsp;nums[i-1] == "0":
                    return 0
                dp.append(dp[i-2])
            else:
                dp.append(dp[i-1] + dp[i-2] if int(nums[i-1:i+1]) <= 26 and nums[i-1] != "0" else dp[i-1])
        return dp[-1]

发表于 2021-08-16 17:39:11 回复(0)
Python
DaDaTheNoob头像 DaDaTheNoob 
class Solution:
    def solve(self, nums: str):
        if nums[0] == '0':
            return 0
        a = 1
        b = 1
        for i in range(1, len(nums)):
            tmp = b if nums[i] != '0' else 0
            if 9 < int(nums[i-1:i+1]) <= 26:
                tmp += a
            a, b = b, tmp
        return b

发表于 2021-04-03 14:46:56 回复(0)
提交观点

问题信息

动态规划
上传者：牛客332641号
难度：
4条回答 4927浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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