LeetCode Letter Combinations of a Phone Number in Javascript

문제

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

접근

Leetcode에서 top intervewed questions을 체크해놓고 하나씩 풀어보고 있는데 계속 백트래킹 문제만 걸린다. 백트래킹 문제를 3문제 정도 풀어봤는데, 대충 어떤 느낌인지는 알겠는데 막상 문제가 나와도 응용이 안되서 풀 수가 없다. 문제를 읽으면 "아 이거 백트래킹 문제겠다" 까지는 알겠는데, 백트래킹 코드를 작성하는게 너무 어렵다. 한 시간 정도 고민하다가 결국 답을 보고 이해했다. 양심에 찔려서 도저히 submit버튼은 누를수가 없었다.

문제는 2~9 사이의 숫자를 랜덤으로 갖는 문자열을 주고 그 숫자조합으로 만들 수 있는 알파벳 조합을 찾아내면 된다. 먼저 map을 통해서 숫자에 맞는 알파벳들을 지정을 해주고 백트래킹으로 순열 알고리즘을 만들면 된다.

let letterCombinations = function(digits) {
    if(!digits.length) return [];
    
    let obj = {
        1: "hello",
        2: "world"
    }
    
    console.log(obj[1]);
    
    let 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'],
    }
    
    let result = [];
    
    function permute(string, index) {
        if(index === digits.length) {
            result.push(string);
            return;
        }
        
        for(let x of map[digits[index]]) {
            console.log(x, map[digits[index]]);
            permute(string+x, index+1);
        }
    }
    permute('', 0);
    return result;
};

정답 코드는 위와 같은데, '' 문자열부터 시작해서 주어진 digits의 첫 번째 char를 먼저 string에 추가한다. 빈 문자열이었던 string에 문자하나가 들어가고 또 permute를 돈다. 이 때 index를 증가시키고 그 index가 digits.length와 같다면 하나의 조합을 만드는데 성공했다는 의미이므로 결과 배열에 추가한다.

"23"이 digits로 입력되었다고 하면 먼저 빈 문자열이 들어가고 첫 번째 permute에서 a가 들어간다.(2의 첫 번째 x) 그리고 또 permute를 돌며 다음 digits인 3의 첫 번째 x인 d가 추가 되고 그 다음 베이스 케이스에 걸려 결과에 추가되고 마지막 트래킹 즉 두 번째 트래킹이었던 digits 3의 다음 문자인 'd'에 대해 같은 알고리즘이 반복된다. 그리고 두 번째 트래킹이 전부 마무리되면 첫 번째 트래킹, 즉 digits의 두 번째 x인 b에 대해 또 알고리즘이 반복된다.

코드를 보면 어떻게 이해가 되는데, 또 다른 방식으로 백트래킹 알고리즘을 짜라고 하면 할 수 있을지 모르겠다. BFS, DFS 같은 경우에는 2~3문제만에 감 잡고 응용을 할 수 있었는데 백트래킹은 더 많이 풀어봐야 할 것같다.