91. Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "111" can have each of its "1"s be mapped into 'A's to make "AAA", or it could be mapped to "11" and "1" ('K' and 'A' respectively) to make "KA". Note that "06" cannot be mapped into 'F' since "6" is different from "06".

Given a non-empty string num containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

backtracking 을 쓰려고 했는데... 잘 안되네요

Solution 1: Runtime: 40 ms - 19.59% / Memory Usage: 14.4 MB - 18.44%

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {}
        return self._dp_helper(s, dp)

    def _dp_helper(self, data, dp):
        # Base Case 1: Empty string
        if not data:
            return 1

        first_call, second_call = 0, 0

        if data in dp:
            return dp[data]

        if 1 <= int(data[:1]) <= 9:
            first_call = self._dp_helper(data[1:], dp)

        if 10 <= int(data[:2]) <= 26:
            second_call = self._dp_helper(data[2:], dp)

        dp[data] = first_call + second_call

        return dp[data]

DP 이용.

if 1 <= int(data[:1]) <= 9: => 한자리씩 0 이 아닌지 확인
first_call = self._dp_helper(data[1:], dp)
=> if 문에서 확인한 자리 이후의 값들도 재귀로 한자리씩 0 이 아닌지 확인

if 10 <= int(data[:2]) <= 26: => 두자리씩 범위 안에 속하는지 확인
second_call = self._dp_helper(data[2:], dp)
=> if 문에서 확인한 자리 이후의 값들도 재귀로 두자리씩 범위 안에 속하는지 확인

그럼 decode 경우의 수 누적 값이 최종적으로 리턴됨