首页 > 试题广场 >

解码方法

[编程题]解码方法

热度指数：7870 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

输入描述:

12可以解码成“AB”，“L”这两种

输出描述:

解码方法的总数

示例1

输入

输出

说明

12可以解码成“AB”，“A，B"这两种

算法知识视频讲解

Python

小吖201908021331253

n = input()
count = [0 for i in range(len(n))]
if  n=="0":
    print(0)
else:
    if n[0]=="0":
        count[0]=0
    else:
        count[0]=1
    if n[1]!="0":
        t1=1
    else:
        t1=0
    if n[0]=="1" or (n[0]=="2" and int(n[1])<=6):
        t2=1
    else:
        t2=0
    count[1]=t1+t2
    for i in range(2,len(n)):
        if n[i]!="0":
            count[i]+=count[i-1]
        if int(n[i-1:i+1])>=10 and int(n[i-1:i+1])<=26:
            count[i] +=count[i-2]
    print(count[len(n)-1])

解析:依然是将对应位置的结果存入数组中，记录状态。在每一个阶段时，考虑当前字符串是否可独立（是否为0），是否可与前一个字符串相结合这两种情况，如果可独立，这是的第i阶段的方法总数就加上前一阶段的方法总数，如果可合并就加上前两个阶段的方法总数，每一个阶段的初始化为零。

发表于 2019-09-22 16:09:16 回复(0)

Python

我要扛offer回家

import sys
s=sys.stdin.readline().strip()
n=len(s)
dp=[1]*n
if int(s[0]+s[1])<=26:
    dp[1]=2
for i in range(2,n):
    if int(s[i-1]+s[i])<=26:
        dp[i]=dp[i-1]+dp[i-2]
    else:
        dp[i]=dp[i-1]
print(dp[-1])

发表于 2019-09-14 19:44:31 回复(0)

Python

贾志统

def func(input_str):
    n = len(input_str)
    dp = [1] * (n+1)
    for i in range(2, n+1):
        if input_str[i-2] == "1" or input_str[i-2] == "2" and int(input_str[i-1]) < 7:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = dp[i-1]
    print(dp[n])


input_str = input() 
func(input_str)

发表于 2019-08-26 22:47:11 回复(0)

Python

欧巴禾

word = input()
dp = [0]*len(word) if word[0]>='1' and word[0]<='9':
    dp[0] = 1 k = word[0]+word[1] if word[1]>='1' and word[1]<='9': if k>='10' and k<='26':
        dp[1] = dp[0]+1  else:
        dp[1] = dp[0] else: if k>='10' and k<='26':
        dp[1] = dp[0] else:
        dp[1] = 0 for i in range(2,len(word)):
    param = word[i-1] + word[i] if word[i]>='1' and word[i]<='9':
        dp[i] = dp[i-1] if param>='10' and param<='26':
            dp[i] = dp[i-1] + dp[i-2] else: if param >= '10' and param <= '26':
            dp[i] = dp[i - 2] else:
            dp[i] = 0 print(dp[len(word)-1])