디코드 방식

A-Z의 문자를 포함하는 메시지는 다음 매핑을 사용하여 숫자로 인코딩할 수 있습니다.

'A' -> "1"
'비' -> "2"
...
'지' -> "26"

인코딩된 메시지를 해독하려면 모든 숫자를 그룹화한 다음 위 매핑의 역순으로 문자로 다시 매핑해야 합니다(여러 가지 방법이 있을 수 있음). 예를 들어 "11106"는 다음과 같이 매핑될 수 있습니다.

"AAJF" 그룹화(1 1 10 6) 포함

"KJF" 그룹화(11 10 6) 포함

(1 11 06)가 "06"와 다르기 때문에 'F'가 "6"에 매핑될 수 없기 때문에 그룹화 "06"가 유효하지 않습니다.

숫자만 포함하는 문자열s이 주어지면 이를 디코딩하는 방법의 수를 반환합니다.

답이 32비트 정수에 맞도록 테스트 케이스가 생성됩니다.

예 1:

입력: s = "12"
출력: 2
설명: "12"는 "AB"(1 2) 또는 "L"(12)로 해독될 수 있습니다.

예 2:

입력: s = "226"
출력: 3
설명: "226"은 "BZ"(2 26), "VF"(22 6) 또는 "BBF"(2 2 6)로 해독될 수 있습니다.

예 3:

입력: s = "06"
출력: 0
설명: 앞에 0이 있기 때문에 "06"을 "F"에 매핑할 수 없습니다("6"은 "06"과 다름).

제약:

1 <= s.length <= 100

s에는 숫자만 포함되며 선행 0이 포함될 수 있습니다.

해결책:

class Solution:
    memo = {}

    def isCorrect(self, n):
        if n[0] == "0":
            return False
        return int(n) >= 1 and int(n) <= 26

    def numDecodingsRec(self, s):
        if len(s) == 0:
            return 1
        if len(s) == 1:
            if self.isCorrect(s):
                return 1
            else:
                return 0
        if s in self.memo:
            return self.memo[s]
        numWays = 0
        if self.isCorrect(s[:1]):
            numWays += self.numDecodingsRec(s[1:])
        if self.isCorrect(s[:2]):
            numWays += self.numDecodingsRec(s[2:])
        self.memo[s] = numWays
        return numWays

    def numDecodings(self, s: str) -> int:
        self.memo = {}
        return self.numDecodingsRec(s)