2023.12.26 Today's Challenge

fabichoi 2023. 12. 26. 23:45

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

Decode Ways - LeetCode

Can you solve this real interview question? Decode Ways - 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

leetcode.com

DP로 푸는 문제

class Solution:
    def numDecodings(self, s: str) -> int:
        if s == "0":
            return 0
        dp_2 = 1
        dp_1 = int(s[-1] != "0")
        i = len(s) - 2
        
        while i >= 0:
            if s[i] == "0":
                dp_0 = 0
            else:
                dp_0 = dp_1
                if (s[i] == "1") or (s[i] == "2" and int(s[i+1]) < 7):
                    dp_0 += dp_2
            i -= 1
            dp_0, dp_1, dp_2 = 0, dp_0, dp_1

        return dp_1