Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列数,按照A-Z对应1-26,问这列数有几种拆分成字符串的方式,DP,只要考虑当前位1-9以及最近两位数10-26的情况



 1 #91
 2 #Runtime: 22 ms (Beats 17.34%)
 3 #Memory: 13.4 MB (Beats 71.65%)
 4 
 5 class Solution(object):
 6     def numDecodings(self, s):
 7         """
 8         :type s: str
 9         :rtype: int
10         """
11         dp = [0] * (len(s) + 1)
12         dp[0] = 1
13         for i in xrange(0, len(s)):
14             if i == 0:
15                 if s[i] == '0':
16                     return 0
17                 dp[i + 1] = 1
18             else:
19                 if 10 <= int(s[i - 1 : i + 1]) <= 26:
20                     dp[i + 1] += dp[i - 1]
21                 if 1 <= int(s[i]) <= 9:
22                     dp[i + 1] += dp[i]
23         return dp[-1]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理