有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。
我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。
由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 ‘a’ 也可以看做是一个 ‘k’ 。但 10 只可能是 ‘j’ ，因为 0 不能编译成任何结果。
现在给一串数字，返回有多少种可能的译码结果。
数据范围：字符串长度满足 0 <n≤90
输入："12"
返回值：2
说明：2种可能的译码结果（"ab" 或"l"）
输入："31717126241541717"
返回值：192
说明：192种可能的译码结果
题目难度：中等
题目来源： 把数字翻译成字符串_牛客题霸_牛客网 (nowcoder.com)
def solve(self , nums: str) -> int:
# your code here
assert solve( "12") == 2
assert solve("31717126241541717") == 192
def solve(nums: str) -> int:
# your code here
if nums == "0" or nums[0] == "0":
return 0
if nums == "10" or nums == "20" or len(nums) == 1:
return 1
for i in range(1, len(nums)):
if nums[i] == "0" and (nums[i-1] != "1" and nums[i-1] != "2"):
print(nums[i], nums[i-1])
return 0
s = [1 for i in range(len(nums)+1)]
for i in range(2, len(nums)+1):
if (nums[i-2] == "1" and nums[i-1] != "0") or (nums[i-2] == "2" and (0 < int(nums[i - 1]) < 7)):
s[i] = s[i-1] + s[i-2]
else:
s[i] = s[i-1]
return s[len(nums)]
assert solve( "12") == 2
assert solve("31717126241541717") == 192
class Solution:
def solve(self , nums: str) -> int:
#排除0
if nums == "0":
return 0
#排除只有一种可能的10 和 20
if nums == "10" or nums == "20":
return 1
#当0的前面不是1或2时，无法译码，0种
for i in range(1, len(nums)):
if nums[i] == '0':
if nums[i - 1] != '1' and nums[i - 1] != '2':
return 0
#辅助数组初始化为1
dp = [1 for i in range(len(nums) + 1)]
for i in range(2, len(nums) + 1):
#在11-19，21-26之间的情况
if (nums[i - 2] == '1' and nums[i - 1] != '0') or (nums[i - 2] == '2' and nums[i - 1] > '0' and nums[i - 1] < '7'):
dp[i] = dp[i - 1] + dp[i - 2]
else:
dp[i] = dp[i - 1]
return dp[len(nums)]
assert Solution().solve( "12") == 2
assert Solution().solve("31717126241541717") == 192
def solve(nums: str) -> int:
def possi(n):
count = n - 1
i = n - 3
while i > 0:
count = count + (i+1)*i//2
i -= 2
return count + 1
result = 1
left = 0
right = 1
while right < len(nums) and nums[left] != '0':
if int(nums[right-1:right+1])>26:
if nums[right] == '0':
return 0
if right - left >= 2:
result *= possi(right - left)
left = right
right += 1
elif int(nums[right-1:right+1]) == 10 or int(nums[right-1:right+1]) == 20:
if right - left >= 2:
result *= possi(right - left + 1)
left = right+1
right += 2
else:
right += 1
else:
if left < len(nums) and nums[left] == '0':
return 0
if left < len(nums)-1:
result *= possi(right - left)
return result
def solve(nums: str) -> int:
index=0
res=1
while index<len(nums)-1:
if 10<int(nums[index:index+2])<20 or 20<int(nums[index:index+2])<27:
try:
if 10<int(nums[index+1:index+3])<20 or 20<int(nums[index+1:index+3])<27:
res*=3
index+=1
else:
res*=2
except:
res*=2
index+=1
return res
assert solve( "12") == 2
assert solve("31717126241541717") == 192