[LeetCode] 17. Letter Combinations of a Phone Number

https://leetcode.com/

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.

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

Example 1:

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

 

Example 2:

Input: digits = ""
Output: []

 

Example 3:

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

Constraints:

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

 

Code :

var letterCombinations = function (digits) {
    if (digits.length === 0) return [];
    // 전화기 버튼 객체
    const btns = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z'],
    };
    let result = btns[digits[0]];
    if (digits.length === 1) return result;

    // 첫 digits로 이루어진 조합은 이미 구했으므로,
    // 주어진 digits 길이-1 만큼만 반복을 돈다. "235" => "35"
    for (let i = 1; i < digits.length; i++) {
        // 이유는 알수없으나 btns 객체가 오염되는 버그가 있어 부득이하게 재정의
        const btns = {
            2: ['a', 'b', 'c'],
            3: ['d', 'e', 'f'],
            4: ['g', 'h', 'i'],
            5: ['j', 'k', 'l'],
            6: ['m', 'n', 'o'],
            7: ['p', 'q', 'r', 's'],
            8: ['t', 'u', 'v'],
            9: ['w', 'x', 'y', 'z'],
        };
        // 추가해야할 버튼의 문자열 배열
        const chars = btns[digits[i]];
        // 문자열 4개짜리 버튼이면 4개를 추가해주어야 한다.
        const isFourChars = digits[i] === '7' || digits[i] === '9';

        // 만들어진 배열을 반복을 돌면서, 새로운 문자열을 더한 배열로 대체한다.
        for (let j = 0; j < result.length; j++) {
            const str = result[j];
            result[j] = [str + chars[0], str + chars[1], str + chars[2]];
            if (isFourChars) result[j].push(str + chars[3]);
        }

        // 2차배열을 flatten해준다.
        result = result.flat();
    }

    return result;
};

 

Solutions Code :

var letterCombinations = function(digits) {
    if (digits.length === 0) return []; // 입력이 비어있는 경우 빈 배열을 반환합니다.

    const phone_map = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; // 숫자에 해당하는 문자들의 매핑을 나타내는 배열입니다.
    const output = []; // 결과를 담을 배열을 초기화합니다.
    backtrack("", digits, phone_map, output); // 백트래킹 함수를 호출합니다.
    return output; // 결과 배열을 반환합니다.

    function backtrack(combination, next_digits, phone_map, output) {
        if (next_digits.length === 0) { // 더 이상 다음 숫자가 없는 경우
            output.push(combination); // 조합을 결과에 추가합니다.
        } else {
            const letters = phone_map[next_digits[0] - '2']; // 현재 숫자에 해당하는 문자들을 가져옵니다.
            for (const letter of letters) { // 각 문자에 대해
                backtrack(combination + letter, next_digits.slice(1), phone_map, output); // 조합을 생성하고 다음 숫자에 대해 재귀 호출합니다.
            }
        }
    }
};

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode