[Python] leetcode91-Decode Ways

leetcode91-Decode Ways

leetcode91-Decode Ways

---

Approch 1 - DFS(Timeout)

Basic Structure

string s.
DFS(s)
  if s == '': 
      cnt += 1
	  return
  
  pick 1 num -> DFS(s[1:])
  pict 2 num -> DFS(s[2:])

Approch 1 - 풀이 (Timeout)

class Solution:
    def numDecodings(self, s: str) -> int:
        def checker(sstr, sel): # (sstr: check string, sel: selected number)
            global cnt
            if sstr == '':                                
                #selects.append(sel[:]) # for checking 
                cnt += 1
                return
            
            if int(sstr[0]) == 0: return

            # Pick 1 num
            sel.append(sstr[0]) 
            checker(sstr[1:], sel)
            sel.pop()

            # Pick 2 nums
            if not 10 <= int(sstr[:2]) <= 26: return
            if len(sstr) >= 2:
                sel.append(sstr[:2])
                if len(sstr) == 2:
                    checker('', sel)
                else:
                    checker(sstr[2:], sel)
                sel.pop()

        #selects = [] # for checking
        global cnt
        cnt = 0 # get counts of case
        checker(s, []) # (val1: check string, val2: selected number)
        #print('ret:', selects) # for checking

        return cnt

=> "111111111111111111111111111111111111111111111" TC Timeout… OTL

---

---

Approach 2 - DP(Success)

• Reference: https://www.dalecoding.com/problems/decode-ways

Basic Structure

Approach 2 - 풀이(Success)

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0] * len(s) + [1]
        for start in reversed(range(len(s))):
            if s[start] == "0":
                dp[start] = 0
            elif start + 1 < len(s) and int(s[start : start + 2]) < 27:
                dp[start] = dp[start + 1] + dp[start + 2]
            else:
                dp[start] = dp[start + 1]
        return dp[0]