LeetCode Letter Combinations of a Phone Number (JavaScript)

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

문제 설명

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

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

Example 2:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 1 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

---

문제 풀이

DFS를 이용하여 문제 풀이

1. 빈 문자열과 시작 인덱스 ('', 0)을 초기로 시작

2. index에 해당하는 digits의 문자를 digitsMap을 통해 검색

3. index의 digits 문자를 통해 문자열을 채워나갈 수 있도록 dfs 재귀호출 -> 만약 index가 digits.length - 1과 같다면 마지막 지점이므로 최종 문자열을 answer에 저장

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    const digitsMap = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }

    const answer = [];
    const dfs = (str, index) => {
        if (index === digits.length - 1) {
            return digitsMap[digits[index]].split('').forEach(word => answer.push(str + word));
        }

        const target = digitsMap[digits[index]];
        for (let j = 0; j < target.length; j++) {
            dfs(str + target[j], index + 1);
        }
    }

    dfs('', 0);

    return answer;
};

---

결론

DFS 알고리즘을 이용하여 해결