Mfcttrf

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);
;

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.

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!