Challenge: phone keypad to letters - return all possible strings

Question

The challenge:

Given a mapping of digits to letters (as in a phone number), and a digit string, return all possible letters the number could represent. You can assume each valid number in the mapping is a single digit.

Example:

If {"2": ["a", "b", "c"], 3: ["d", "e", "f"], ...} then "23" should return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

My iterative solution:

const digitMap = (digiStr) => {
 const digitMapping = {
 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 length = digiStr.length; 
 if (length === 1) return digitMapping[digiStr]; // in case of single digit strings
 const indexes = []; // index addresses of charsets, in order
 for (let i = 0; i < length; i++) {
 indexes.push(0);
 }
 let nextI = length === 2 ? 0 : 1; // current spot of nextI in indexes
 const possibleStrs = []; // for final answer of possible permutations
 let str = ''; 
 let endCount = 0; // if all addresses in indexes are at their end, then break while loop
 while (true) {
 console.log(indexes);
 for (let i = 0; i < length; i++) {
 str += digitMapping[digiStr[i]][indexes[i]];
 if (indexes[i] === digitMapping[digiStr[i]].length - 1) {
 endCount += 1;
 }
 }
 possibleStrs.push(str);
 str = '';
 if (endCount === length) {
 break;
 }
 endCount = 0;
 // increment last item in indexes as long as it < length of corresponding inner char array
 if (indexes[indexes.length - 1] < digitMapping[digiStr[digiStr.length - 1]].length - 1) {
 indexes[indexes.length - 1] += 1;
 }
 else {
 indexes[indexes.length - 1] = 0;
 // increment nextI as long as < length of corresponding inner array
 if (indexes[nextI] < digitMapping[digiStr[nextI]].length - 1) {
 indexes[nextI] += 1;
 }
 else {
 // otherwise shift position of nextI in indexes array
 // if next position of nextI not end of indexes array
 // shift nextI 1 spot forward in indexes
 if (nextI + 1 < length - 1) {
 nextI += 1;
 indexes[nextI] += 1;
 }
 else {
 // else reset all indexes to 0, starting from position 1
 for (let i = 1; i < indexes.length; i++) {
 indexes[i] = 0;
 }
 // increment first item in indexes
 indexes[0] += 1;
 nextI = 1; // place nextI at position 1
 }
 }
 }
 }
 return possibleStrs;
}
console.log(digitMap("2"));
console.log(digitMap("23"));
console.log(digitMap("234"));
console.log(digitMap("2345"));
console.log(digitMap("23456"));

Produces the correct output for all test cases. Any alternative approaches--recursive or iterative--to cleaning up the conditional logic would be greatly appreciated.

Answer 1

Interesting question;

High Level Overview

The code is close to good, I definitely would not go for a recursive solution. These challenges often have at least 1 test with a really long string.

Naming

• Some of your naming choices are unfortunate:
  • possibleStrs -> I would go for possibleStrings, or combinations, or out
  • I prefer <verb><thing> over <thing><verb>; so mapDigits over digitMap or even generatePossiblePhoneWordCombinations

Comments

• I like your approach to commenting

JSHint.com

• Your code is only missing 2 semicolons, consider using http://jshint.com/ to perfect your code

Production Code

• Remove all references to console.log()
• You are mixing variable declarations and logic, I would group the variable declarations up front

Alternatives

• The below could use a built-in function

  const indexes = []; // index addresses of charsets, in order
  for (let i = 0; i < length; i++) {
   indexes.push(0);
  }
  

  could be

  const indexes = Array(length).fill(0);
  

Counter Proposal

The logic you are using afterwards is a little convoluted, and is hard to read. In essence, you can convert the input string to an array, and use that array to keep track of your state.

// "23" should return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
function mapDigits(s){
 const digitMapping = {
 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']
 }
 //Get the digits, ignore ones and zeroes
 let digits = s.split('').filter(i => i > 1);
 let out = [], tmp = [];
 //Some shortcuts
 if(!digits.length){
 return out;
 }
 if(digits.length == 1){
 return digitMapping[digits[0]];
 }
 //We're still here, prep out and digits (shift modifies digits)
 out = digitMapping[digits.shift()];
 while(digits.length){
 const nextLetters = digitMapping[digits.shift()];
 tmp = out;
 out = [];
 tmp.forEach(s => nextLetters.forEach(c => out.push(s+c))); 
 }
 return out;
}
console.log(mapDigits("23"));

• konijn: As a comment, the approach from @Zefick is very different and superior to our approaches.

Answer 2

Too long for a comment...

The problem as presented seems to have much in common with the string permutations problem in terms of solution structure.

You should be able to do something similar to: https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string with slight modification to get a compact recursive formulation.

Pseudo code below:

solution(string digits, string prefix="", array<string> outputs)
 if digits empty then
 add prefix to outputs
 else
 currentDigit := digits.get(0)
 remainingDigits := digits.remove(0);
 for each character in listOfCharsForDigit[currentDigit] do
 solution(remainingDigits, prefix+character, outputs)
 endfor
 endif

Hope that helps...