haklee.py

"""TC: O(n), SC: O(1)

아이디어: 
뒷 k개의 글자를 디코딩 하는 경우의 수를 f(k)라고 하자.
f(k)는 다음의 두 경우의 수를 더한 값이다.
  - 뒷 k개의 글자 중 첫 글자가 디코딩 가능한 경우, 뒷 k-1글자를 디코딩하는 경우의 수
  - 뒷 k개의 글자 중 앞 두 글자가 디코딩 가능한 경우, 뒷 k-2글자를 디코딩하는 경우의 수
즉, f(k) = (앞 두 글자 판별)*f(k-2) + (앞 한 글자 판별)*f(k-1)


SC:
- tabulation 과정에서 값 2개만 계속 유지한다.
- 즉, O(1).

TC:
- f(k) 구하는 식: O(1)
    - 두 글자가 디코딩 가능한지 판별: O(1)
    - 첫 글자가 디코딩 가능한지 판별: O(1)
- 위의 f(k)를 구하는 것을 s의 길이에서 2를 뺀 수만큼 루프, 즉, O(n)
- 종합하면 O(n).
"""


class Solution:
    def numDecodings(self, s: str) -> int:
        # init
        x, y = 1, int(int(s[-1]) != 0)  # f(0), f(1)
        # tabulation
        for i in range(len(s) - 2, -1, -1):  # 뒷 k개 글자의 시작 글자가 s[i]
            # f(k-2), f(k-1)을 f(k-1), f(k)로
            x, y = y, (x * (10 <= int(s[i : i + 2]) <= 26)) + (y * (int(s[i]) != 0))
        return y