[LeetCode] 91. Decode Ways - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/decode-ways/

Decode Ways - LeetCode

유형 : 동적 계획법(Dynamic Programming)

문제 설명

숫자만 포함된 문자열 s가 주어지면 이를 디코딩하는 방법의 수를 return 하는 문제이다.

 

A~Z까지의 문자들은 아래와 같이 숫자로 인코딩할 수 있다.

'A' -> '1'
'B' -> '2'
...
'Z' -> '26'

인코딩된 메시지를 디코딩 하려면 위의 매핑을 반대로 사용하여 모든 숫자를 그룹화한 다음 다시 문자로 매핑해야 한다(그룹화하는 방법은 여러 가지가 있다). 예를 들어 "11106"은 다음과 같이 매핑할 수 있다.

• (1 1 10 6)으로 그룹화하여 매핑한 "AAJF"
• (11 10 6)으로 그룹화하여 매핑한 "KJF"

(1 11 06)으로는 그룹화 될 수 없다. 왜냐하면 "6"과 "06"은 다르기 때문에 "06"이 'F'와 매핑된다고 볼 수 없다.

Example 1)
Input: s = "12"
Output: 2

Example 2)
Input: s = "226"
Output: 3

Example 3)
Input: s = "06"
Output: 0

제한사항

• 1 <= s.length <= 100
• s은 0과 양의 정수들로 이루어져 있다.

문제 풀이

성공 코드

from typing import List

class Solution:
    def numDecodings(self, s: str) -> int:
        str_length = len(s)
        if str_length == 0:
            return 0
        
        dp = [None]*(str_length+1)
        dp[-1] = 1
        
        last_char = s[-1]
        if int(last_char) == 0:
            dp[str_length-1] = 0
        else:
            dp[str_length-1] = 1
            
        for idx in range(str_length-2,-1,-1):
            single_num = int(s[idx])
            single_count = 0
            if single_num > 0:
                single_count = dp[idx+1]
            
            double_num = int(s[idx:idx+2])
            double_count = 0
            if 10 <= double_num <= 26:
                double_count = dp[idx+2]
                
            count = single_count + double_count
            dp[idx] = count
            
        return dp[0]

시간 복잡도 : O(n)

n은 s의 크기이다.

공간 복잡도 : O(n)

n은 s의 크기이다.