[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.

 

Constraints:

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

 

Hint 1

문제를 각 문자에 대한 처리조건을 부여함으로써, 문제를 축소시킬 수 있다.

Hint 2

숫자 하나에 대해 변환될 수 있는 경우의 수는: 0, 1 , 2중 하나이다.

 

 

Approach

1. Back ~ front 방향으로 각 부분 문자열에서 도출 될 있는 방법 수를 담는 배열을 만든다.

var numDecodings = function(s) {

    const n = s.length;
    const dp = new Array(n);
   
};

 

2. i번째 문자가, 0일때와 0이 아닐때로 분기된다. 0일때는, 어느 문자로든 매핑되지 않으므로 경우의 수는 0, 그 외의 경우는 1 혹은 2가지 방법이 있다.

var numDecodings = function(s) {
    if (!Number(s[0]) return 0; // 예외 케이스
    const n = s.length;
    const dp = new Array(n).fill(0);
    dp[s.length] = 1;
    
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] !== '0') {
        
        } else {
            dp[i] = 0;
        }
    }
};

3. i번째 문자가 1일때, 혹은 i번째 문자가 2이면서 i+1번째 문자가 6이하면 ( 10 ~ 19 , 20 ~ 26)이면, 이전 문자와 더불어 디코딩의 경우의 수가 2가지로 분기한 상황이다. 따라서 해당 경우,  i + 2번 사건까지 경우의 수 + 이전 (i+1) 경우의 수의 합이 i번째 경우의 수가 된다.

var numDecodings = function(s) {
    if (s[0] === '0') return 0;
    const n = s.length;
    const dp = new Array(n).fill(0);
    dp[n] = 1;
    
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] !== '0') {
            dp[i] = dp[i + 1];
            
            if (s[i] === '1' || (s[i] === '2' && s[i+1] <= '6')) {
                dp[i] += (dp[i + 2] || 0)
            }
        } else {
            dp[i] = 0;
        }
    }
    
    return dp[0]
};