[Leetcode 91] 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 mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

 

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

 

생각 과정

예시)

2222 -> 2 22 2, 2 2 2 2, 22 2 2, 22 22
1121 -> 11 21, 1 12 1, 11 2 1        

Brute Force

가능한 경우로 다 왔다갔다 하면서 invalid 확인, valid면 ++1
length가 최대 100이라.. 이렇게 진행해도 될지 좀 걱정스럽긴 함
순서대로 한 글자씩 확인하며 진행. 지금 글자랑 다음 글자 이었을 때 말이 되면 그것도 진행, 아니면 하나만 진행.

1	1	1	0	6
1	1	1	0 (X)
		10		6
	11		0 (X)
11		1	0 (X)
		10		6

recursive하게 짜볼까,, 했는데 네번째에서 0을 굳이 계속 확인해야 하는 게 너무 별로인 것 같았다.

확인했던 걸 계속 확인하고 있다!

그래서 거꾸로 읽는 걸 생각해봤다.

 

index	0	1	2	3	4
value	1	1	1	0	6
진행	2	1	1	0	1

맨 뒤에서부터 확인한다.

3번째 1을 보자. 거꾸로 진행하는 거니까 0, 1번째는 생각하지 말고, 106이라고 생각하자.

106에서 1을 처리하는 방법은 두가지다.

1. 1 / [...]
2. 10 / [...]

한 자리로 사용하거나 다음 글자와 함께 두 자리로 사용하거나. 이 두 가지의 경우를 합하면 된다.

1의 경우는 결국 뒤의 글자들인 06을 구성하는 경우의 수이고, 

2의 경우는 다다음 글자인 6을 구성하는 경우의 수이다.

dp[len-1 -n]
= ( n번째 글자가 유효한 digit인가; 0만 아니면 됨 ) * dp[n-1] + ( n번째 글자, n-1번째 글자가 유효한 digit인가; 10~26) * dp[n-2]

( dp는 글자 순서랑 반대 순서! )

 

이렇게 점화식을 작성하고, 첫번째 항을 초기화한다.

사실 상 뒤에서 두번째 숫자부터 위의 점화식이 유효하게 적용될 수 있긴 한데 dp[n-2]가 걸린다. 그래서 dp에 먼저 1을 넣어줬다.

두자리도 만들 수 있으면 1을 더할 수 있게.

 

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        num_map = []
        dp = [1]
        for i in range(1, 27):
            num_map.append(str(i))
        
        # 1  1  1  0  6
        end = s[len(s)-1]
        if end == "0":
            dp.append(0)
        else:
            dp.append(1)
                
        for i in range(len(s)-2, -1, -1):
            start = s[i]
            temp = 0
            if start != "0":
                temp += dp[-1]
            if start+end in num_map:
                temp += dp[-2]
            dp.append(temp)
            end = start
        # print(dp)
        return dp[-1]