[LeetCode] 91. Decode Ways

91. Decode Ways

Medium

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 grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

 

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

---

문제 풀이

• 주어진 숫자 문자열에서 얼마나 많은 아스키코드 문자로써 알파벳으로 구성되어 있는지 구해야한다.
• A 는 1, B 는 2 .... Z 는 26 으로, 한 자리 숫자의 알파벳, 두 자리 수의 알파벳이 존재할 수 있다.
• 각 자리마다 1, 2 자리 수의 조합을 확인해야하기 때문에 완전탐색 문제로 볼 수 있으며, 제한 사항은 문자열의 최대길이가 100이다. 
• 재귀함수를 사용시 브랜치는 2개로 선택이 되며, 길이가 최대 100이기 때문에 2^100 까지 진행되어 시간초과가 될 수 있다.
• 예를 들어 326에서 첫번째 자리에서 3을 선택하고 두번째에서 2를 선택하는 것과 두번째 자리에서 32를 선택하는 것은 중복이 된다. 
• lru_cache 를 사용하여 이미 처리된 인덱스에 접근 했을때 메모이제이션으로 리턴해줘야한다. 
• 그리고 종료 조건으로 마지막에 한자리를 선택 했을때와 두자리를 선택했을때를 처리해준다.
• 두자리를 선택했을때 첫 자리가 0 이어도 처리를 해줘야한다. 

두번째 풀이법은 Dynamic Programming 을 사용할 수 있다. 

• 첫번째 자리를 기본 값으로 1로 설정한다, DP 리스트에서 최종 값은 문자열의 길이이다.
• 두번째 1 인덱스의 자리를 0 이면 0 아니면 1로 설정한다.
• 2부터 시작하여 전자리가 0이 아니면 한 칸 이전의 값을 현재 위치에 할당한다.
• 그리고 현재 위치에서 앞의 두자리가 알파벳 숫자 범위 안에 있다면 현재 위치에 2자리 전 값을 더해준다.
• 예를 들어 12 라면, dp[0] = 1 로 시작했을때 맨 앞자리는 무조건 한개의 알파벳을 생성할 수 있기 때문에 1개가 된다.
• 그리고 반복문으로 인덱스 1 위치와 0위치를 확인하는데, 인덱스 1 위치에 0 이 아닌 숫자가 있다면 그자리의 개수를 가져온다.
• 만약 인덱스 0, 1 위치에 숫자도 가능하다면 2 자리 이전의 값을 현재 위치에 더해준다.
• 결과적으로 처음 시작은 1 로 시작하고 두 자리 숫자가 선택될 수 있다면 2 자리 이전 값을 더해주면서 진행한다. 2 자리가 가능할때 부터 알파벳으로 구성하는 문자열이 선택된 숫자만큼 증가하기 때문이다.

소스 코드

재귀 함수 + 메모이제이션

class Solution:
    def numDecodings(self, s: str) -> int:
        @lru_cache(maxsize=None)
        def rec(idx):
        	# 마지막에 한 자리수를 선택햇을때 종료조건
            if idx == len(s):
                return 1
            # 마지막에 두 자리수를 선택햇을때 종료조건
            # 두 자리 숫자중 첫번째가 0이면 0 리턴
            if s[idx] == '0':
                return 0
            # 두 자리를 선택하면 1을 리턴
            if idx == len(s) - 1:
                return 1
            
            answer = rec(idx + 1)
            if int(s[idx:idx+2]) <= 26:
                answer += rec(idx + 2)
            
            return answer
        return rec(0)

Dynamic Programming

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0 for _ in range(len(s) + 1)]
        dp[0] = 1
        dp[1] = 0 if s[0] == '0' else 1
        for i in range(2, len(dp)):
            if s[i - 1] != '0':
                dp[i] = dp[i - 1]
            two_digit = int(s[i - 2: i])
            if two_digit >= 10 and two_digit <= 26:
                dp[i] += dp[i - 2]
        return dp[len(s)]