Posted on 2023-12-25 23:04
Uriel 閱讀(42)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出一列數(shù)，按照A-Z對(duì)應(yīng)1-26，問這列數(shù)有幾種拆分成字符串的方式，DP，只要考慮當(dāng)前位1-9以及最近兩位數(shù)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]