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' ]