[4코3파] #307. Leetcode 1-D Dynamic Programming (2)

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (307일차)
[4코1파] 2023.01.13~ (299일차)
[4코3파] 2023.10.01 ~ (37일차)

Today :

2023.11.06 [307일차]

Leetcode 1-D Dynamic Programming

[7] 91. Decode Ways

https://leetcode.com/problems/decode-ways/

문제 설명

주어진 숫자 문자열을 디코딩하여 가능한 모든 방법의 수를 찾는 문제이다.
'A'부터 'Z'까지의 각 알파벳은 1부터 26까지의 숫자로 매핑된다.
'A'는 1로, 'B'는 2로, 'Z'는 26으로 매핑된다.
주어진 숫자 문자열은 '0'으로 시작하지 않기 때문에 "01", "02" 등의 숫자는 유효하지 않는다. 주어진 문자열은 비어 있지 않으며, 'A'에서 'Z'까지의 알파벳 대문자로만 구성된다.

문제 풀이 방법

주어진 문자열을 순회하면서 각 숫자를 현재 숫자로 간주한다.
그 전 숫자와 결합하여 디코딩 방법의 수를 계산한다. 여러 경우의 수를 따져가면서 가능한 모든 디코딩 방법을 계산하고, 중복 계산을 피하기 위해 중간 결과를 저장해가며 문제를 해결한다.

내 코드

 class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s):1}

        def dfs(i):
            if i in dp:
                return dp[i]

            if s[i] == "0":
                return 0
            
            res = dfs(i+1)
            if (i+1 < len(s) and (s[i]=="1" or s[i]== "2" and s[i+1] in "0123456")):
                res += dfs(i+2)
            dp[i] = res
            return res

        return dfs(0)
            

---

여담