LeetCode #91 Decode Ways

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #91 Decode Ways

문제 풀이

dp로 풀 수 있겠다는 생각은 들었지만 제약조건 체크에 너무 많은 시간을 쏟아버렸다. 제약 조건을 체크하는 문제가 최근 코테에 빈번히 출제된다는 점에서 좋은 문제라 생각한다. 현재 자리에 대해 유효성 검증과 앞자리와 결합하여 2자리로 만들 수 있는지 여부가 중요하다.

• 현재 자리가 0일 경우
  • 앞 자리가 1이나 2라면 앞자리를 포함한 두 자리로 구성해야 하므로 i - 2째 자리의 가짓수와 동일
  • 앞 자리가 1이나 2가 아니라면 유효하지 않으므로 0 반환
• 현재 자리가 0이 아닌 경우
  • 앞 자리가 1이면 현재 자리도 유효하고 앞자리와 결합하여 두 자리로도 구성이 가능하므로 i - 2위치와 i - 1 위치의 가짓수를 더한 값이다.(i -2는 두 자리 수로 구성했을 때, i - 1은 한 자리 수로 구성했을 때)
  • 앞 자리가 2라면 1부터 6까지인지 확인하여 포함되면 i - 2와 i - 1번째 가짓수를 더한 값
  • 그 외엔 두 자리 구성이 불가하므로 i - 1과 동일

python 코드

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        elif len(s) == 1:
            return 1
        dp = [0] * len(s)
        dp[0] = 1
        char = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
        if s[1] == "0":
            if s[0] in char[1:3]:
                dp[1] = dp[0]
            else:
                return 0
        else:
            if s[0] == "1":
                dp[1] = 2
            elif s[0] == "2" and s[1] in char[1:7]:
                dp[1] = 2
            else:
                dp[1] = dp[0]
        if len(s) > 1:
            for i, c in enumerate(s[2:], 2):
                if s[i] == "0":
                    if s[i - 1] in char[1:3]:
                        dp[i] = dp[i - 2]
                    else:
                        return 0
                else:
                    if s[i - 1] == "1":
                        dp[i] = dp[i - 2] + dp[i - 1]
                    elif s[i - 1] == "2" and s[i] in char[1:7]:
                        dp[i] = dp[i - 2] + dp[i - 1]
                    else:
                        dp[i] = dp[i - 1]
        return dp[-1]