leetcode0017 - Letter Combinations of a Phone Number / Medium / Typescript

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

 

백트래킹(Backtracking)

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다. 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 갑니다. 해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것입니다.

https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

const letterMap = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];

위 예시의 경우, digits[0]에 해당하는 2의 letter는 abc이다.
이 경우, ['a', 'b', 'c'] 라는 string array를 순회하면서, backtrack(1, 'a'), backtrack('1, 'b'), backtack(1, 'c') 를 호출한다. 이때, digits[1]에 해당하는 '3'의 letter인 'def' 를 순회히면서 'a', 'b', 'c'와 combination을 만든다. digits는 두 글자 조합이고, letter 조합도 두 글자여야 하기 때문에 함수의 첫번째 인자가 2 가 되면 정답셋에 해당 단어 combination을 담아준다. 즉, digits의 문자 길이가 될 때 까지 재귀적으로 backtrack 함수를 호출한다.

1 a - backtrack(1, 'a')
2 ad - backtrack(2, 'ad')
2 ae - backtrack(2, 'ae')
2 af - backtrack(2, 'af')

1 b - backtrack('1, 'b')
2 bd - backtrack(2, 'bd')
2 be - backtrack(2, 'be')
2 bf - backtrack(2, 'bf')

1 c - backtack(1, 'c')
2 cd - backtrack(2, 'cd')
2 ce - backtrack(2, 'ce')
2 cf - backtrack(2, 'cf')

Time Compexity, Space Complexity O(3^N) or O(4^N)

N: digits 문자열의 길이
letterMap을 보면 글자수가 3 또는 4이기에, 가능한 조합의 수 역시 3^N 또는 4^N

 

function letterCombinations(digits: string): string[] {
    if(digits === '') return [];

    const letterMap = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    const ans = [];

    const backtrack = (idx, str) => {
        if(idx === digits.length) {
            ans.push(str);
        } else {
            letterMap[digits[idx]].split("").forEach((letter) => {
                backtrack(idx+1, str+letter);
            }) 
        }
    }
    backtrack(0, "");
    return ans;
};