17. Letter Combinations of a Phone Number

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

2~9의 숫자 배열이 주어질 때 해당 숫자로 만들 수 있는 문자열을 모두 찾는 문제다.

Solution

Backtracking

문제에서 길이 제한이 4개로 주어졌다. 결과를 전부 반환하기 위해서도 최소 (3~4 ^ N)의 시간이 필요하다. 백트래킹으로 모든 경우의 수를 계산한다.

Algorithm

• phoneMap을 통해 각 숫자에 해당하는 문자를 매핑한다.
• digits의 길이가 0일경우 바로 빈배열을 반환하고 아닐 경우 초기 값으로 첫번째 result를 만든다. 이때 result는 클로저의 자유 변수다.
• 이후 result 에 addDigitToResult를 통해 새 문자를 넘겨주면 result에 새로운 문자가 추가된 새result로 바꾼다.
• 위 과정을 끝까지 반복하여 result를 반환한다.

var letterCombinations = function(digits) {
  const phoneMap = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
  }
  if (digits.length === 0) return [];
  let result = phoneMap[digits[0]].split('');
  const addDigitToResult = (digit) => {
    // if (!phoneMap[digit]) return;
    const newResult = [];
    const addLetter = phoneMap[digit];
    result.forEach((el) => {
      for (let letter of addLetter) {
        newResult.push(el + letter);
      }
    });
    result = newResult;
  }
  
  for (let digit of digits.slice(1)) {
    addDigitToResult(digit);
  }
  return result;
};