[Leetcode][Python] 91. Decode Ways

리트코드 / 파이썬 / 91. Decode Ways

leetcode.com/problems/decode-ways/

Decode Ways - LeetCode

풀이 방법

* Example 2:

   Input: s = "226"

   Output: 3

   Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

 

0~9까지의 숫자로 구성된 string을 받고, A~Z까지 각각 1~26까지라고 했을 때 가능한 경우의 수를 구하는 문제다.

Example 2의 경우 2+26(BZ), 22+6(VF), 2+2+6(BBF)로 3가지가 답이다.

 

Backtracking으로도 풀 수는 있겠으나, 시간이 오래걸리고 중복된 연산이 많으므로 DP로 푼다.

 

길이가 len(s) + 1 인 linear list를 아래와 같이 만들고, 기저 사례를 먼저 저장한다.

(기저 사례를 dp[0]부터 만들어야하는 이유는 아래 표를 보면 이해된다.)

 

"dp[0] = 1, dp[1] = 첫번째 숫자가 0이 아니면 1, 0이면 0"

 

dp[0]이 1인 이유는 0!=1이기 때문이다. 그리고 코드의 맨 첫줄에서 s가 빈 string이면 0을 return할 것이다.

 

Example 2, s = "226" 인 경우

dp[0]	dp[1]	dp[2]	dp[3]
	2	22	226
1	1	2 (2, 22 가능 dp[0] + dp[1] = 2)	3 (6, 26 가능 dp[1] + dp[2] = 3)

 

dp[3]을 예시로 설명해보면,

dp[3]의 값은 22 + 6 경우의 수와, 2 + 26 경우의 수의 합이다.

(물론 노란색으로 칠한 부분이 decoding될 수 없다면 더하지 않는다.)

 

즉, 각각의 식에서 22를 만들 경우의 수, 2를 만들 경우의 수는 각각 dp[1], dp[2]가 되기 때문에

dp[3] = dp[1] + dp[2] = 3이다.

 

소스 코드

class Solution(object):
    result = 0
    def numDecodings(self, s):
        """
        https://leetcode.com/problems/decode-ways/
        :type s: str
        :rtype: int
        """
        if s == '0':
            return 0

        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 1 if s[0] >= '1' else 0

        for i in range(2, len(s) + 1):
            if s[i - 1] >= '1':
                dp[i] += dp[i - 1]
            if int(s[i - 2 : i]) >= 10 and int(s[i - 2 : i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[len(s)]