JavaScript Algorithms question: how do I use recursion to solve such a combination problem?

Question

we have a digit letter map that looks like this

const digitsLetters = new Map([
    ["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']],
  ]);

The question asks us to return the all possible letter combinations that the number could represent. For example, if we have "23" then first digit 2 maps to ['a', 'b', 'c'] and second digit maps to ['d', 'e', 'f'] and we end up getting ["ad","ae","af","bd","be","bf","cd","ce","cf"].

I have found a way to produce such a combination between two arrays.

// this will output ["ad","ae","af","bd","be","bf","cd","ce","cf"]
['a', 'b', 'c'].map(char1 => ['d', 'e', 'f'].map(char2 => char1 + char2)).flat(2)

So I thought I could just recursively apply this algorithm for such digit until I hit the last one. I think it is doable. However I had a hard time implementing the solution. Can someone please help me?

Yes, recursion can be used. I recommend flattening out the `map`s into `for` loops and then seeing if you can figure out from there how to create the recursive formulation. I think that may make it clearer for you. — Sumner Evans, Mar 16 '21 at 23:31
Does this answer your question? [Cartesian product of multiple arrays in JavaScript](https://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) — Sumner Evans, Mar 16 '21 at 23:31

score 0 · Answer 1 · answered Mar 16 '21 at 23:59

You can basically just use map method to get array from you Map data based on string param and them implement Cartesian product algo.

const data = new Map([
  ["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']],
]);

function f(str, map) {
  const result = [];
  const arr = str.split('').map(c => map.get(c))

  function r(data, n = 0, prev = []) {
    if (n === data.length) {
      return result.push(prev.slice())
    }

    for (let i = 0; i < data[n].length; i++) {
      prev[n] = data[n][i]
      r(data, n + 1, prev.slice())
    }
  }

  r(arr)

  return result;
}

console.log(f('23', data))
console.log(f('358', data))

score 0 · Answer 2 · answered Mar 17 '21 at 00:20

Something like this

const digitsLetters = new Map([
  ["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 foo = (arr, result = []) => {
  if (arr.length === 0) return result;
  
  const value = arr.shift();
  if (result.length === 0) return foo(arr, value);
 
  const newResult = [];
  
  result.forEach((el) => {
    value.forEach((el2) => {
      newResult.push(el + el2);
    });
  });

  return foo(arr, newResult);  
};

const boo = (str) => foo(str.split('').map((symbol) => (digitsLetters.get(symbol))));

console.log(boo(''));
console.log(boo('2'));
console.log(boo('23'));
console.log(boo('232'));

score 0 · Accepted Answer · answered Mar 17 '21 at 10:25

Let's consider the cartesian product f(E, F) with an example

assume E is like ['12', '13']

then you get candidates a and b, which I name as F = ['a', 'b']

f(E, F) = E x F would give ['12a', '13a', '12b', '13b']

(note that ExF is the same type of E, an array of string)

now you can recurse on the digits given

g([digit, ...otherDigits], E) => {
  candidates = m.get(digit)
  EF = cartesianProduct(E, candidates)
  return g(otherDigits, EF)
}

Note that the initialization on E should not be the empty array, but an array of length 1 whose sole element is the "neutral" element (empty string for strings)

const data = new Map([
  ["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 f = (E, F) => E.flatMap(e => F.map(f => e + f))
const g = ([digit, ...otherDigits], E=['']) => digit ? g(otherDigits, f(E, data.get(digit))) : E
console.log(g('23'.split('')))
console.log(g('234'.split('')))

JavaScript Algorithms question: how do I use recursion to solve such a combination problem?

3 Answers3