[Python] LeetCode - Decode Ways

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

Decode Ways - LeetCode

* 문제해석: 1 -> 'A', 2 -> 'B', 3 -> 'C' ... 26 -> 'Z' 이런식으로 디코딩을 할 수 있다.

  Incoding된 문자열을 Decoding하려면 모든 숫자를 '그룹화'한 다음 다시 문자로 mapping 해야한다.

  ex) "11106"을 mapping하는 경우

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)
• (1 11 06)은 06이 매핑될 수 없으므로 제외("6"과 "06"은 다름)

 

1. s의 길이 +1 만큼 dp배열을 선언하고 마지막 인덱스에 1을 넣어준다.

   s의 마지막 자리가 0이면 dp[length - 1] = 0 아니면 1을 넣어준다.

  

2. length-2부터 0까지 i를 1씩 줄여나가면서 dp테이블을 갱신해준다.

   (마지막자리부터 첫번째 자리순으로 갱신)

 

# DP테이블을 갱신하는 과정은 다음과 같다. 우선 "212325"를 예로 들면, "212325"는

   "2 / 12325", "21 / 2325"로 나눌 수 있다. (26을 넘어가면 디코딩이 되지않으므로 212 / 325부터는 제외)

   여기서 두 케이스는 또 "1 / 2325", "12 / 325"로 나누고 "2 / 325", "23 / 25"와 같이 나눌 수 있다.

   결국 앞에 한자리 또는 두자리로 끊어서 나눌 수 있고 12 / 325에서 구한 325에 대한 dp값은

    2 / 325와 같이 중복되므로 Overlapping Subproblem(겹치는 부분(작은) 문제)이 발생한다.

    또한, 12 / 325에서 구한 dp값과 1 / 2325에서 구한 dp값을 합하면 12325에 대한 경우의 수이므로

    Optimal Substructure(최적 부분구조)를 만족한다.

 

class Solution:
    def numDecodings(self, s: str) -> int:
        if s == '0':
            return 0
        
        length = len(s)
        dp = [0] * (length + 1)
        dp[-1] = 1
        dp[length - 1] = 0 if s[-1] == '0' else 1
        
        for i in range(length-2, -1, -1):
            single = int(s[i])
            single_count = 0
            # 한자리 끊은 수가 디코딩이 가능한 경우
            if single > 0:
                single_count = dp[i + 1]
            
            double = int(s[i: i+2])
            double_count = 0
            # 두자리 끊은 수가 디코딩이 가능한 경우
            if 10 <= double <= 26:
                double_count = dp[i + 2]
            
            count = single_count + double_count
            dp[i] = count
        
        return dp[0]