[leetcode] 91. Decode Ways

Problem Link

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

Description

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.

I/O Example

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 2

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

---

Approach #1

ds: array
algo: dp

dp table index 자릿수..  s.length + 1
0123
1120 

123456
        ^
    
ex) “123”
0123
0123
1123

dp index 0 “ “ -> 
         1  “1” -> 1
         2  “12” -> “2”
               
1자리 = s.slice(     //1 
2자리 - s.slice(     //12

1자리 > 0 
26 >= 2자리 >=10 

dp 테이블을 만들어 bottom-up 방식으로 접근하면 정말 쉽게 풀리는 문제다.

dp 배열은 s.length + 1 의 길이를 갖고, 배열의 인덱스는 문자열의 길이를 의미한다.
만약 인풋으로 들어오는 s문자열이 "123"이라고 가정한다면,
dp table의 구성은 다음과 같다.

index 0 1 2 3
      1 1 0 0

인덱스 0은 " "(빈문자열 일때),
인덱스 1은 "1"(문자열 길이가 1일때),
인덱스 2는 "12"(문자열 길이가 2일때),
인덱스 3은 "123"(문자열 길이가 3일때) decode 될수 있는 가짓수이다.

인덱스 1은 방법이 1가지 이므로 1이될것이고,
인덱스가 0일때는 방법이 0가지 이지만 로직상 인덱스 2일때를 처리해주기 위해 1로 초기셋팅 해준다.
인덱스 2일때("12" 문자열)는 "1" "2" / "12" 두가지 방법으로 decode 될수 있는데 이 경우는 dp테이블의 i-1(한자리 잘랐을때), i-2(두자리 잘랐을때)번 인덱스의 항목을 가져와 더한 값이 된다.

Solution #1

var numDecodings = function(s) {
    //edge case
    if(s[0]==="0") return 0;
    if(s.length===1) return 1;
    
    const dp = new Array(s.length+1).fill(0);
    dp[0]=1;
    dp[1]=1;
    
    for(let i=2;i<s.length+1;i++){
        let oneN=Number(s.slice(i-1,i));
        let twoN=Number(s.slice(i-2,i));
        //앞의 한문자 볼때
        if(1<=oneN && oneN<=9) dp[i]+=dp[i-1];
        //console.log(dp[i]) ->0
        //앞의 두문자 볼때
        if(10<=twoN && twoN<=26) dp[i]+=dp[i-2];
    }
    return dp[s.length];
    
};

N: s.length

Time Complexity

O(N^2)

N만큼 for문을 돌며 문자열 s를 한자리, 두자리 slice(O(N))로 잘라보기 때문에 N^2의 시간복잡도를 갖는다.

Space Complexity

O(N)

dp 테이블 배열 만들때 O(N+1)만큼의 공간이 필요함.

Review

1. 언젠가 풀어본 문제 같아서 처음 보자마자 1자리, 2자리 단위로 잘라서 보아야 한다는것, dp 문제라는 것 까지는 캐치가 빨랐다. 다만 문제는 dp table을 어떻게 구성해야할지 기억이 안났다는것....
2. 30분정도 지났을때 dp table의 index를 자릿수로 두고 bottom-up 방식으로 풀어야 한다는 것이 떠올라 45분안에 겨우 풀수 있었다.
3. 풀었던 문제도 다시보자!
4. 분명 한달전에 풀었던 문제인데 ... ㅎ 역시 반복만이 답이다.

TIL

• slice(start idx, end idx)

---

Approach #2

Solution #2

Time Complexity

Space Complexity

Review

TIL

---