时间戳

首页 > 解决方案 > JavaScript 算法问题：如何使用递归来解决这样的组合问题？

javascript - JavaScript 算法问题：如何使用递归来解决这样的组合问题？

问题描述

我们有一个看起来像这样的数字字母图

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']],
  ]);

问题要求我们返回数字可以代表的所有可能的字母组合。例如，如果我们有"23"第一个数字2映射到['a', 'b', 'c']，第二个数字映射到['d', 'e', 'f']，我们最终得到["ad","ae","af","bd","be","bf","cd","ce","cf"].

我找到了一种在两个数组之间产生这种组合的方法。

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

所以我想我可以递归地将这个算法应用于这样的数字，直到我打到最后一个。我认为这是可行的。但是，我很难实施该解决方案。有人可以帮帮我吗？

标签： javascriptalgorithmrecursion

解决方案

您基本上可以使用基于字符串参数的map方法从您的数据中获取数组，并且它们实现笛卡尔积算法。Map

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

推荐阅读