[LC] 91. Decode Ways

[seungriyou]

https://leetcode.com/problems/decode-ways/

Approach

Idea 1: 1D DP (Space O(n))

주어진 s에 대해 len(s) + 1 길이의 리스트인 dp를 초기화 한다.

dp[i] = i 번째 숫자를 보고있을 때, 여기까지 decode 가능한 경우의 수

decode 가능한 값의 범위가 1 ~ 26이므로, decode 가능한 경우는 다음과 같이 두 가지이다.

#	확인해야 하는 값	확인해야 하는 값(코드)	확인해야 하는 범위	이용해야 하는 값
1-step	현재 보고 있는 숫자 한 개	s[i - 1]	1 ~ 9 이내인지	dp[i - 1]
2-step	현재 보고 있는 숫자와 이전 것 (총 두 개)	s[i - 2:i]	10 ~ 26 이내인지	dp[i - 2]

따라서 다음과 같이 DP를 수행한다.

• dp[0], dp[1]에 대해서: base condition 설정

• dp[2]~ 에 대해서:

  1. 1-step 확인 및 업데이트
  2. 2-step 확인 및 업데이트

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

    # base condition
    dp[0] = 1
    dp[1] = 0 if s[0] == "0" else 1

    for i in range(2, n):
        # 1-step 전
        if 1 <= int(s[i - 1]) <= 9:
            dp[i] += dp[i - 1]

        # 2-step 전
        if 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]

    return dp[n - 1]

Idea 2: O(1) DP (Space O(1))

1D DP를 살펴보면, 이전 값인 dp[i - 1]과 그 이전 값인 dp[i - 2]만 필요하다는 사실을 알 수 있다.

따라서 리스트를 가질 필요 없이, 그 두 값을 저장하는 변수 prev1, prev2를 가지고 값을 트래킹하면 O(1) space로 최적화 할 수 있다.

Complexity

• Time: O(n)
• Space: (1D) O(n) / (constant) O(1)