[DP] 91. Decode Ways 这种题,不懂也罢🙄

Goal

  • return the number of ways to decode a string (any number ≤26)
  • ‘226’ → [2,2,6] [22, 6] [2,26]

Strategy 1

  • 0不能算作单独一个数 → ‘210’ 不可拆为[21,0]
  • use hash table to store calculated values
  • recursive + memo

Code

class Solution:
@lru_cache(maxsize=None)
def helper(self, s, i):

if i==len(s):
return 1
elif s[i] == '0':
return 0
elif i==len(s)-1:
return 1

current = self.helper(s,i+1)
if int(s[i:i+2])<=26:
current += self.helper(s,i+2)

return current


def numDecodings(self, s: str) -> int:


return self.helper(s,0)

Strategy 2

  • Use DP bottom up approach
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] =='0':
return 0

oneStep = 1
twoStep = 1

for i in range(1,len(s)):

current = 0
if s[i]!='0':
current = oneStep
if int(s[i-1:i+1])>=10 and int(s[i-1:i+1])<=26:
current+=twoStep

twoStep = oneStep
oneStep = current

return oneStep

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store