Find all letter Combinations of a Phone Number

Question

The task

is taken from LeetCode

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

My solution

(I've been told I should provide additional information to my solution otherwise I get downvoted.)

is based on backtracking. Why I choosed that approach? Well, whenever you encounter a task where you have to combine or permutate things, then backtracking is a possible approach.

But if you know a better one, then please go ahead. Otherwise I only got generic questions to my code: Can you make it faster, cleaner, more readable, etc.?

Also I'm interested in functional programming. So, if you got a good functional approach, feel free to post it here, too. Other than that, I'm always interested in a different perspective. So, if you got a fancy or conservative approach, please feel free to post them here.

Imperative approach

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (digits === '') { return []; }
  const strDigits = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
  };

  if (digits.length === 1) { return [...strDigits[digits]]; }
  const res = [];
  const combine = (cur, n) => {
    if (cur.length === digits.length) {
      res.push(cur);      
      return;
    }

    [...strDigits[digits[n]]].forEach(x => {
      combine(cur + x, n + 1);
    });

  };

  combine('', 0);
  return res;
};

Functional approach

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (digits === '') { return []; }

  const strDigits = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
  };

  const combine = (cur, n) => cur.length === digits.length 
    ? cur
    : [...strDigits[digits[n]]].flatMap(x => combine(cur + x, n + 1));

  return combine('', 0);
};

Answer 1

Make it faster

This is only improvements on the algorithm you have used.

There are a few ways to improve the performance. The majority are minor a few % points improvement but due to the complexity ~\$O(3^n)\$ quickly sum up to be worth the effort.

The last step

There is a very common mistake in recursive code that will nearly always give a huge performance gain (30-40% in this case).

First think about why you are using a recursive function. In this case you are using it to hold the current cur combination until it is complete. In other words you are using the recursive call to place cur on a stack, the stack being the call stack. The call stack is easy to use (transparent) but comes with the cost of stacking everything within the functions context, including all that is not relevant to the next step.

The common error in recursion is to place the exit clause at the beginning of the function. In the snippet below, you recurse at #A with cur + x which pushes a new context to the call stack, then at point #B you check to see if cur + x now as cur is the final length to exit.

So at point #A you have all the information needed to know whether or not to exit, thus wasting the creation on a new context.

Redundant recursion call

  // For seven digit number (ignoring 9) the following calls combine 3280
  const combine = (cur, n) => {
    if (cur.length === digits.length) { // code point #B
      res.push(cur);      
      return;
    }
    [...strDigits[digits[n]]].forEach(x => combine(cur + x, n + 1)); // code point #A
  };

Exit one recursion step earlier

To avoid that extra call by testing for the length early

  // For seven digit number (ignoring 9) the following calls combine 1093 times
  const FINAL_LEN = digits.length - 1
  const combine = (cur, n) => {
       if (cur.length === FINAL_LEN) { // only one char remaining to add
           [...strDigits[digits[n]]].forEach(x => res.push(cur + x));

       } else { [...strDigits[digits[n]]].forEach(x => combine(cur + x, n + 1)) }
  };

So for a 7 digit number (ignoring "9") the complexity is \$O(3^n)\$ saving 2187 needless pushes to the call stack. About a 30-40% saving in performance.

Example ~40% performance improvement

The following example has a ~40% improvement in performance when processing a set of random number strings in the range 2 - 79999999. (I did note that as the range grew there was a small drop in the improvement with a ~37% for 10 digits, and 34% for 12 digits and is likely due to the array size growth and memory management overhead)

Other improvements.

• Avoid capturing (closure) of function's combine state by using for loops.
• Using an pre processed array of digits, avoiding the need to build the array [...strDigits[digits[n]]]
• Convert the digits string to numbers and use indexed array to lookup characters to reduce JS hashing to locate items in strDigits

The rest of the changes are just style as performance testing iteration required many versions and my style slowly intruded into the final iteration

I moved ALPHAS previously strDigits outside the function because that is my style (avoid repeated processing) and does not provide an improvement. You would normally capture it in a IIF closure.

const ALPHAS = ",,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(",").map(a => [...a]);
function letterCombinations(numStr) {
    const alphas = ALPHAS; // local scope reference for shallower scope search
    const nums = [...numStr].map(Number);
    const res = [];
    const count = nums.length - 1;
    (function combine(n, cur) {
        if (n === count) {
            for (const char of alphas[nums[n]]) { res.push(cur + char) }
        } else {
            for (const char of alphas[nums[n]]) { combine(n + 1, cur + char) }
        }
    })(0, "");
    return res;
}

Functional

My distaste for functional code has another example of why it is to be avoided and decried at every opportunity. You functional code a an order of magnitude slower than your imperative solution.

Not only was it slow but the fans on the machine kicked in so I looked at the load. There was the equivalent to an extra core running near flat out (JS GC and memory management threads) and power consumption jumped by 20W!!! (thats a 3rd of a solar panel) over running the tests without the functional solution.

The list below shows the comparative results for set of random digits to 8 digits long. (an operation is one test cycle)

BM67....: Time:  3,875µs OPS: 258 100% Total time:  3,798ms for 980 operations
OP imp..: Time:  6,370µs OPS: 156  60% Total time:  6,307ms for 990 operations
OP func.: Time: 84,988µs OPS:  11   4% Total time: 82,439ms for 970 operations

Answer 2

whenever you encounter a task where you have to combine or permute things, then backtracking is a possible approach.

True. It is not necessarily the best though (in fact it is rarely the best).

In this particular case, the problem naturally maps to finding the next combination. In turn, it is no more than an increment of a number in some fancy numbering system. In your example, the minimal possible string is ad. Subsequent increments yield ae, then af, then ('f' + 1 is d and a carry bit does carry) bd, etc.

Consider implementing the increment/next method directly. The space complexity will definitely benefit; and it is trivial to convert into a generator. The time complexity is likely to also benefit, depending on the use case.

PS: thank you for posting your train of thoughts.

Answer 3

I think your functional approach is very nice, and scores high points for readability. As long as the recursion wasn't causing performance issues, that's how I'd approach it.

However, it's not very efficient, and as vnp points out, listing permutations is really just a matter of counting from 1 to "the number of combinations" in a mixed base numbering system.

mixed base counting

These are easy implement, and it's worth going through the exercise, because assuming you have a utility that does the mixed base counting for you, the solution to the original problem will be both straightforward and efficient:

function mixedBaseCounter(bases) {
  let cnt = 0
  let maxCnt = bases.length ? [...bases].reduce((m, x) => m * x, 1) : 0
  let digits = bases.map(() => 0)

  const increment = (i = 0) => {
    digits[i] = (digits[i] + 1) % bases[i]
    if (digits[i] == 0) increment(i + 1)
  }

  return {
    [Symbol.iterator]: function* () {
      while (cnt++ < maxCnt) {
        yield digits.join('')
        increment()
      }
    }
  }
}

This uses ECMA script's iterable interface. Note the above implementation has the least significant bit on the left (easily changed, if you need to).

Let's verify it counts correctly in binary:

[...mixedBaseCounter([2, 2, 2])]
// [ '000', '100', '010', '110', '001', '101', '011', '111' ]

And that it handles mixed bases:

console.log([...mixedBaseCounter([2, 3])])
// [ '00', '10', '01', '11', '02', '12' ]

Try it online!

applying it to the problem

Now the solutions becomes:

function letterCombinations(digits) {

  const strDigits = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
  }

  const letterOptions = [...digits].map(x => strDigits[x])
  const bases = [...letterOptions].map(x => x.length)
  const masks = mixedBaseCounter(bases)

  return [...masks].map(m =>
    [...m].map((x, i) => letterOptions[i][x]).join('')
  )
}

where each "mask" (or number, within the mixed base numbering system) chooses one combination.

Note also we no longer need to treat the empty string as a special case.

Try it online!

Answer 4

I see a couple of simplifications that could be made:

A feature of ecmascript-6 that could be used here is default parameters:

const combine = (cur = '', n = 0) => {

Then the first call to that function doesn't need to pass any parameters:

combine();

---

The arrow function in the imperative approach feels too brief to warrant the need for brackets:

[...strDigits[digits[n]]].forEach(x => {
  combine(cur + x, n + 1);
});

So that could be shortened to a single line:

[...strDigits[digits[n]]].forEach(x => combine(cur + x, n + 1));

But if that is longer than your desired maximum length of a line of code, pull out the arrow function:

const combineNext = x => combine(cur + x, n + 1);
[...strDigits[digits[n]]].forEach(combineNext);

Actually, in an imperative solution, I might expect to see a for...of loop, which should be faster:

for (const x of [...strDigits[digits[n]]]) {
  combine(cur + x, n + 1);
}

---

I considered suggesting that the keys of strDigits be integers instead of string literals, each element in digits would be a string so the types would then be different.