3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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"));
\$\endgroup\$
  • 1
    \$\begingroup\$ As a comment, the approach from @Zefick is very different and superior to our approaches. \$\endgroup\$ – konijn Jul 24 at 17:33
2
\$\begingroup\$

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...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.