91. Decode Ways

Description

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

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

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

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”). In this case, the string is not a valid encoding, so return 0.

Constraints:

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

Submitted Code

class Solution:
    def numDecodings(self, s: str) -> int:
        memo = {}

        def dfs(i):
            if i == len(s): return 1          # 마지막 문자의 경우의 수는 1
            if s[i] == '0': return 0          # '0'으로 시작하면 계산 불가
            if i in memo:   return memo[i]

            res = dfs(i + 1)

            if i + 1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
                res += dfs(i + 2)

            memo[i] = res
            return res

        return dfs(0)

Runtime: 0 ms | Beats 100.00%
Memory: 19.51 MB | Beats 13.68%

i번째 인덱스부터 끝까지 해석 가능한 경우의 수를 ‘memo’ 딕셔너리에 저장하는 방법이다.

s = “11106”

dfs(0)
├── dfs(1)
│   ├── dfs(2)=0+1=1
│   │   ├── dfs(3)=0
│   │   └── dfs(4)=1
│   │
│   └── dfs(3)=0(memo 사용)
│
└── dfs(2)=1(memo 사용)

return 2

Other Solutions

1st

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0':
            return 0
        
        n = len(s)
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1

        for i in range(2, n + 1):
            one = int(s[i - 1])
            two = int(s[i - 2:i])

            if 1 <= one <= 9:
                dp[i] += dp[i - 1]
            if 10 <= two <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

time complexity: 𝑂(𝑛)
space complexity: 𝑂(𝑛)

뒤에서부터 쌓아가는 재귀 호출과 달리 앞에서부터 현재 경우의 수 = 이전 경우들의 합으로 나아가는 방법으로, Fibonacci 수열과 비슷한 구조다. 맨 앞 dp[0]은 빈 문자열 상태일 때도 1로 카운트하기 위해 사용된다.