[리트코드] 17. Letter Combinations of a Phone Number

안녕하세요. 개발조각입니다.😊

이번 문제는 제 머리로 해결 못할 것 같아서 답을 찾아서 풀어보았습니다.

---

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

Letter Combinations of a Phone Number - LeetCode

이문제는 재귀 순열을 이용해서 풀었습니다.

문제가 문자열이 주어지면 숫자가 나타낼 수 있는 가능한 모든 문자 조합을 반환하라는 문제이기 때문에

순열이 필요하다고 생각이 들었고 순열을 풀 거면 재귀로 풀어야 된다고 생각했습니다.

 

저는 아래의 블로그를 보고 풀었습니다.

https://ha-young.github.io/2021/algorithm_javascript/LeetCode-17_Letter_Combinations_of_a_Phone_Number_DFS-BFS/

[Javascript] LeetCode - 17. Letter Combinations of a Phone Number (DFS&BFS)

---

해결방안

var letterCombinations = function(digits) {
    if(!digits.length) return [];
    
    const map = {
        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 result = [];
    function permute(str, idx) {
        if(idx === digits.length) {
            result.push(str);
            return;
        }
        
        for(let alpha of map[digits[idx]]) {
            permute(str+alpha, idx+1);
        }
    }
    permute('', 0);
    return result;
};

 

if(!digits.length) return [];

아래와 같이 빈 문자열일 경우를 먼저 미리 제어를 해주었습니다.

Input: digits = ""
Output: []

 

const map = {
    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'],
}

2~9까지에 해당되는 알파벳을 map형식으로 매칭 해줍니다.

 

const result = [];
function permute(str, idx) {
    if(idx === digits.length) {
        result.push(str);
        return;
    }

    for(let alpha of map[digits[idx]]) {
        permute(str+alpha, idx+1);
    }
}
permute('', 0);

return result;

이제 재귀를 사용해서 풀어보았습니다.

 

 

const result = [];
function permute(str, idx) {
    console.log('처음',str, idx);
    if(idx === digits.length) {
        result.push(str);
        return;
    }

    for(let alpha of map[digits[idx]]) {
        console.log('중간',str, idx);
        permute(str+alpha, idx+1);
    }
    console.log('끄읏',str, idx);
}
permute('', 0);
return result;

어떻게 돌아가는지 이해가 안 되시는 분들을 위해(저를 위해) 콘솔을 3가지로 넣어보았습니다.

console.log('처음',str, idx); // permute함수 안에서 최상단
console.log('중간',str, idx); // for of안으로
console.log('끄읏',str, idx); // permute함수 안에서 마지막

이런 식으로요.

 

그러면 아래와 같은 결과가 나옵니다.

한눈에 파악하기 쉽게

처음: 핑크, 중간: 엘로우, 끄읏: 블루로 넣었습니다.

 

if(idx === digits.length) {
    result.push(str);
    return;
}

'처음'에 있는 idx가 digits.length와 같다면

result에 push를 해주면 됩니다.