LeetCode----Decode Ways

来源:转载

LeetCode----Decode Ways,有需要的朋友可以参考下。

Decode Ways

A message containing letters fromA-Zis being encoded to numbers using the following mapping:

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

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message"12", it could be decoded as"AB"(1 2) or"L"(12).

The number of ways decoding"12"is 2.

分析:

动态规划题,注意,输入会有很多不合法的情况,比如‘100’之类的,这种情况下decoding方式为0。

不合法的情况有:串长度为0;串以0开头;串中出现00;串中出现30,40,50等串。

代码:

class Solution(object): def numDecodings(self, s):""":type s: str:rtype: int"""f = {-1: 1}s_len = len(s)if s_len == 0 or s[0] == '0':return 0f[0] = 1i = 1while i < s_len:if s[i] == '0' and (s[i - 1] > '2' or s[i - 1] == '0'): return 0if s[i] == '0': f[i] = f[i - 2]elif 10 <= int(s[i-1:i+1]) <= 26: f[i] = f[i - 1] + f[i - 2]else: f[i] = f[i - 1]i += 1return f[s_len - 1]

版权声明:本文为博主原创文章,未经博主允许不得转载。


分享给朋友:
您可能感兴趣的文章:
随机阅读: