Keypad Combos

Given a string of digits from 2-9, return all possible letter combinations from the digits on the phone keypad below:

 1    2    3
     ABC  DEF
 4    5    6
GHI  JKL  MNO
 7    8    9
PQRS TUV WXYZ

For example, “23” creates the following:

[
  'AD', 'AE', 'AF',
  'BD', 'BE', 'BF',
  'CD', 'CE', 'CF'
]

One possibility is a recursive approach. For each letter in a digit, append it to all previous sub-results. Digits have either 3 or 4 letters, so for a string with n digits, the worse-case runtime is O(4^n).

const keypad = {
  1: [],
  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']
}

function keypadCombinations(str) {
  if (str.length == 0) {
    return [""]
  }

  let digit = str[0]
  let chars = keypad[digit]
  let substr = str.substring(1)
  let combos = keypadCombinations(substr)
  let newCombos = []

  for (let i = 0; i < chars.length; i++) {
    let c = chars[i]

    for (let j = 0; j < combos.length; j++) {
      let newstring = c + combos[j]
      newCombos.push(newstring)
    }
  }

  return newCombos
}

Here are some sample results:

let x = keypadCombinations("2")
let y = keypadCombinations("23")
let z = keypadCombinations("234")
console.log(x)
console.log(y)
console.log(z)

[
  'A', 'B', 'C'
]
[
  'AD', 'AE', 'AF',
  'BD', 'BE', 'BF',
  'CD', 'CE', 'CF'
]
[
  'ADG', 'ADH', 'ADI', 'AEG',
  'AEH', 'AEI', 'AFG', 'AFH',
  'AFI', 'BDG', 'BDH', 'BDI',
  'BEG', 'BEH', 'BEI', 'BFG',
  'BFH', 'BFI', 'CDG', 'CDH',
  'CDI', 'CEG', 'CEH', 'CEI',
  'CFG', 'CFH', 'CFI'
]