6
\$\begingroup\$

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.

enter image description here

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);
};
\$\endgroup\$

4 Answers 4

2
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ Is there a use case where you would prefer functional over imperative (a general question and not related to this problem)? \$\endgroup\$ Jun 10, 2019 at 20:13
  • \$\begingroup\$ BTW: Some stuff you wrote are quite genius and i could have wrote it myself, e.g. using of IIFE, move the ALPHAS outside of the functions, ... . It's so clear once you see it, but when I wrote it I thought, my code was quite good. But it wasn't I still have to learn a lot .....and also learn to apply what I already know. Thanks again for pointing out my mistakes. \$\endgroup\$ Jun 10, 2019 at 20:38
  • \$\begingroup\$ @thadeuszlay There is no reason I would use a functional approach in javascript unless it (JS) was modified to allow function calls to be multi threaded. IE call to myFunc(...blah) is run in a new thread returning on an implied await. I do not buy the no side effects argument as it is defensive (protecting poor coding from itself) rather than encouraging good coding skills. There is good reason functional coding is a realm of academia and seldom seen in the industry sector as it provides no benefit over good traditional coding paradigms. \$\endgroup\$
    – Blindman67
    Jun 10, 2019 at 20:53
  • \$\begingroup\$ I spent a few months learning FP, because I thought it would improve my coding skills, e.g. by reading books, solving puzzles using FP, etc.. I now feel it was a waste of my time. What would you recommend for someone who wants to improve his coding skills, e.g. some books, projects, ...? \$\endgroup\$ Jun 10, 2019 at 21:00
  • \$\begingroup\$ @thadeuszlay The best way to gain skill is to write, not just small solutions but big projects 10,000+ lines. Big is when bugs start to dominate and your skill to write well is paramount to keep it all working. If you are stuck for a project, write a game as they can be amongst the most difficult code challenges there are (write from the ground up, don't use frameworks or libraries). And always keep in mind segregate and ENCAPSULATE or you will spend more time hunting bugs than writing code. \$\endgroup\$
    – Blindman67
    Jun 10, 2019 at 21:18
8
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

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

I see a couple of simplifications that could be made:

A feature of 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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