LeetCode Decode Ways (JavaScript), (DFS, Memoization)

링크 : https://leetcode.com/problems/decode-ways/description/

문제 설명

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

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"). In this case, the string is not a valid encoding, so return 0.

Constraints:

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

---

문제 풀이

일반적인 dfs방식으로 문제를 접근할 경우 (1글자, 2글자 의 선택에 대해 재귀적으로 반복하게되면 O(2^n)의 시간 복잡도를 가진다.

결국 문자열이 길어지면 시간 초과라는 오류가 발생한다.

이러한 문제를 해결하기 위해 DFS에 Memoization을 적용하여 불필요한 연산을 줄일 수 있다. (O(n)의 시간 복잡도를 가짐)

접근 방법

• 특정 index에서 검사하는 부분을 중복해서 검사하지 않도록 memo(Map)을 통해 특정 index의 res값을 저장해두어 사용
• dfs 리턴 조건
  • index가 s길이인 경우 끝에 도달한 것이므로 1리턴 (가능한 경로)
  • memo에 특정 index가 이미 존재하는 경우 (해당 index를 통한 검사는 이미 이루어짐, memo에 값을 읽어와 사용)
  • s문자열의 index값이 0인 경우 불가능한 값이므로 0리턴
• dfs 재귀 경로
  1. 한 글자 검사 (`dfs(index + 1)`)
  2. 두 글자 검사(`dfs(index + 2)`)
     • 단, 두 글자 검사는 index가 유효한 범위내에 존재하고 2글자가 유효한 범위내(10~26사이)인 경우 탐색 진행
• 현재 index를 기준으로 한 글자, 두 글자 탐색을 진행한 뒤 res 값을 memo에 저장 (추후 불필요한 연산을 막기 위해)
• 최종적으로 res값 리턴

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
    if (s[0] === '0') {
        return 0;
    }

    const memo = new Map();

    const dfs = (index) => {
        // 끝까지 도달 -> 1증가
        if (index === s.length) {
            return 1;
        }

        // 이미 계산된 적이 있다면 저장 값 반환
        if (memo.has(index)) {
            return memo.get(index);
        }

        // 0이면 진행 불가
        if (s[index] === '0') {
            return 0;
        }

        // 한 글자 선택
        let res = dfs(index + 1);

        // 두 글자 선택
        if (index + 1 < s.length) {
            const tmp = parseInt(s.substring(index, index + 2));
            if (tmp >= 10 && tmp <= 26) {
                res += dfs(index + 2);
            }
        }

        memo.set(index, res);
        return res;
    }

    return dfs(0);
};

---

결론

일반 적인 dfs로 쉽게 접근했지만 문자열이 길어질수록 O(2^n)의 시간 복잡도의 알고리즘으로 인해 시간 초과 문제가 발생했고,

이러한 문제를 Memoization을 적용하여 불필요한 연산을 줄여 O(n)의 시간 복잡도로 문제를 해결.

재귀를 도는 과정에서 불필요한 연산을 줄이는게 문제의 핵심