【题目】

Amessage containing letters from A-Z is being encoded to numbers using thefollowing mapping:

 

'A'-> 1

'B'-> 2

...

'Z'-> 26

Given anencoded message containing digits, determine the total number of ways to decodeit.

 

Forexample,

Givenencoded message "12", it could be decoded as "AB" (1 2) or"L" (12).

 

Thenumber of ways decoding "12" is 2.

 

按照编码规则将信息中的字母进行编码,给定一个编码过的信息,返回解码的方法总数。

 例如:“12”---->2种[“AB”,“L”]

 

【思路】

本题宜用动态规划:

共有三种情况:

l  s[i-2]和s[i-1] 两个字符是10----26之间但不包括10和20这两个数时,有两种编码方式,比如23------>[“BC”,“W”],所以dp[i] = dp[i-1]+dp[i-2]

l  s[i-2]和s[i-1] 两个字符10或20这两个数时,有一种编码方式,比如10------>[“J”], 所以dp[i] = dp[i-2]

l  s[i-2]和s[i-1] 两个字符不在上述两种范围时,编码方式为零,比如27,比如01,所以dp[i] = dp[i-1]

 

【Python实现】

 

# -*- coding: utf-8 -*-
"""
Created on Thu Aug 10 09:22:16 2017
 
@author: Administrator
"""
 
class Solution(object):
    def numDecodings(self, s):
       """
       :type s: str
       :rtype: int
       """
       if s=="" or s[0]=='0': return 0
       dp=[1,1]
       for i in range(2,len(s)+1):
           if 10 <=int(s[i-2:i]) <=26 and s[i-1]!='0':#编码方式为2
                dp.append(dp[i-1]+dp[i-2])
           elif int(s[i-2:i])==10 or int(s[i-2:i])==20:#编码方式为1
                dp.append(dp[i-2])
           elif s[i-1]!='0':#编码方式为0
                dp.append(dp[i-1])
           else:
                return 0
       #print(dp[len(s)])
       return dp[len(s)]
 
 
if __name__ == '__main__':
   S= Solution()
    s= "1220"
   S.numDecodings(s)


 

 

 

 

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐