[4코3파] #286. Leetcode 91. Decode Ways

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

START :

[3코1파] 2023.01.04~ (286일차)
[4코1파] 2023.01.13~ (278일차)
[4코3파] 2023.10.01 ~ (16일차)

Today :

2023.10.16 [286일차]

91. Decode Ways

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

문제 설명

주어진 문자열에 대하여 'A'는 1, 'B'는 2 ... 'Z'는 26으로 해당 알파벳을 해당 숫자로 디코드 할 때,
주어진 문자열을 디코딩 할 수 있는 최대 방법을 return 한다.

문제 풀이 방법

brute force의 경우 O(2^n) 임
dynamic programming으로 푸는데,
dynamic programming이 너무 어려워서 찾아보니까
dp에서도 memoization인 top-down 과 Tabulation bottom-up 방법이 있는 걸 알게됐고,
세부 문제를 핸들링하는 부분에서도 memoization이나 tabulation 하는 문제 유형들의 패턴이 있음을 알게 되긴했다. 근데 알게되긴했는데 이해 안되거든요..

해당 문제는 dp[i] = dp[i+1] + dp[i+2] 로 cache를 저장해나가는 top-down
memoization으로 풀면 O(n) 으로 풀 수 있다.
이 문제는 베이스라인은 숫자는 1-26 사이에서 디코딩 되기 때문에 매핑되는 숫자가 둘째자리이면 0123456에 해당 될때만, 그리고 0으로 시작하면 다른 수로 조합되지 않는 다는 조건을 잘 생각하고 풀어줘야 한다.

내 코드

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)

증빙

여담

디피 개어렵네 진짜