Posted on 2023-12-25 23:04
Uriel 阅读(8)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
给出一列数，按照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]