[LeetCode] 91. Decode way

A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1 'B' -> 2 ... 'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

 

해결법

숫자로 이루어진 문자열을 하나씩 읽어들이면서 현재 숫자로 인해 만들 수 있는 경우의 수를 차근차근 만들어 가는 DP방식의 문제 풀이 법으로 접근했다. 또한, 중복된 계산을 막기 위해 메모이제이션을 진행할 것인데 결국에는 두단계전의 경우의 수와 바로 전의 경우의 수만을 가지고 현재 문자열의 경우의 수를 구하는 것이기 때문에 변수는 2개만 사용해도 충분하다고 생각했다. 

 

우선 생각해봐야하는 부분이 두가지라고 생각했다. 

첫번째로는 숫자를 하나씩 읽어나갈때 현재 숫자와 이전 숫자로 2자리 숫자를 만들었을때 10 ~ 26 사이의 숫자인 경우.

 - 현재 숫자가 10- 26사이의 숫자를 만들 수 있는 수라면, 두자리를 만들어서 문자로 decode하는 방식과 한자리만으로 decode하는 방식 이 가능하고 그 말은 즉 두자리를 문자로 decode했을때는 현재 숫자와 바로이전 숫자 이전까지의 숫자들로 만든 decode 경우의수 + 한자리 만으로 문자를 decode했을 때의 바로 이전 숫자까지들로 만든 decode 경우의 수 가 현재 숫자까지로 decode가 가능한 모든 경우의 수라고 보여졌다. 

두번째로는 현재 숫자가 0인 경우의 처리 .

 - 현재 숫자가 0인경우에는 의미있는 문자열이 되려면 앞자리가 1 또는 2인경우에만 10, 20으로 decode시 대응하는 문자열을 가질 수 있다.  앞자리가 1,2가 아닌데 0인 경우에 만들 수 있는 문자열의 경우의 수는 0이다.

 

 

class Solution(object):
    def numDecodings(self, s):
        if s == '': return 0
        first = (0,0)
        second = (0,1) if int(s[0]) != 0 else (0,0)
        can_make = 0
        
        for i in range(len(s)) :
            cur_num = int(s[i])
            if second[0] ==1 or (second[0] ==2 and cur_num <7):
                can_make = first[1] + second[1] if cur_num != 0 else first[1]
            else :
                can_make = second[1] if cur_num !=0 else 0
            first = second
            second = (cur_num, can_make)
            
        return second[1]