电话键盘键的字母组合

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

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