javascript - 电话键盘按键的字母组合

Question

我有一个关于 JavaScript 中电话键盘键的字母组合的问题。我使用 DFS 递归编写了一个解决方案。但它没有按预期工作。我是 JavaScript 新手，但用 Ruby 编写的代码类似。

问题在于从电话键盘获取所有可能的字母组合。

输入：“23”

输出：[“ad”、“ae”、“af”、“bd”、“be”、“bf”、“cd”、“ce”、“cf”]。

使用下面的代码，它在“af”处停止。输出为 ["ad", "ae", "af"]。我不确定为什么这段代码没有移动到“2”的第二个字母，即“b”。

const 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"]
};

let result = [];

let letterCombinations = function(digits) {
  if (digits.length == 0) {
    return []
  };

  let stack = [];
  dfs(digits.split(''), 0, stack)

  return result
};

function dfs(digits, index, stack) {
  const currentLetters = map[digits[index]]

  for (i = 0; i < currentLetters.length; i++) {
    stack.push(currentLetters[i])

    if (index == digits.length - 1) {
      result.push(stack.join(''))
      stack.pop()
    } else {
      dfs(digits, index + 1, stack)
      stack.pop()
    }
  }
}

console.log(letterCombinations("23"));

标签： javascriptrecursionmicrosoft-distributed-file-system

Answer 1

您需要i在 for 循环中声明，否则它是全局的，并且在每个递归步骤中不断增加。

利用for (let i = 0; i < currentLetters.length; i++)

const 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"]
};

let result = [];

let letterCombinations = function(digits) {
  if (digits.length == 0) {
    return []
  };

  let stack = [];
  dfs(digits.split(''), 0, stack)

  return result
};

function dfs(digits, index, stack) {
  const currentLetters = map[digits[index]]
  
  // declare the loop variable!
  for (let i = 0; i < currentLetters.length; i++) {
    stack.push(currentLetters[i])

    if (index == digits.length - 1) {
      result.push(stack.join(''))
      stack.pop()
    } else {
      dfs(digits, index + 1, stack)
      stack.pop()
    }
  }
}

console.log(letterCombinations("23"));