JavaScript如何用递归处理列表生成所有符合跳转规则的字符串？

问题拆解 #

• 核心是多分支路径遍历，同一个position下的每个可选对象都是独立分支，需要全覆盖遍历
• 提前按position分组是最优预处理方案，避免每次递归都遍历全表查找对应位置的对象
• 递归终止条件：跳转后的position超过所有position的最大值，此时得到完整字符串

具体实现代码 #

function generateAllStrings(arr) {
  // 预处理：按position分组，同时计算最大position值
  const posMap = {}
  let maxPos = 0
  arr.forEach(item => {
    const pos = item.position
    if (!posMap[pos]) posMap[pos] = []
    posMap[pos].push(item)
    if (pos > maxPos) maxPos = pos
  })

  const result = []

  // 深度优先遍历递归函数
  function dfs(currentPos, currentStr) {
    // 终止条件：当前位置超过最大值，存入结果
    if (currentPos > maxPos) {
      result.push(currentStr)
      return
    }
    // 当前位置无可用对象直接返回
    if (!posMap[currentPos]) return
    // 遍历当前位置所有可选对象，每个对象对应一个独立分支
    posMap[currentPos].forEach(item => {
      const newStr = currentStr + item.letter
      const nextPos = item.position + item.jump
      dfs(nextPos, newStr)
    })
  }

  // 初始调用：从position=1、空字符串开始遍历
  dfs(1, '')
  return result
}

// 测试用例
const input = [
  {position: 1, jump: 1, letter: "b"},
  {position: 1, jump: 2, letter: "b"},
  {position: 1, jump: 1, letter: "c"},
  {position: 2, jump: 2, letter: "e"},
  {position: 2, jump: 1, letter: "e"},
  {position: 3, jump: 1, letter: "a"},
  {position: 4, jump: 1, letter: "t"},
  {position: 4, jump: 1, letter: "d"},
]
console.log(generateAllStrings(input))
/* 输出结果和示例完全一致：
[ 'bet', 'bed', 'beat', 'bead', 'bat', 'bad', 'cet', 'ced', 'ceat', 'cead' ]
*/

实现说明 #

• 预处理阶段同时完成分组和最大position计算，减少不必要的遍历
• 结果数组通过闭包共享，无需每次递归传递，降低内存开销
• 所有分支会被完整遍历，不会遗漏同一个position下的多对象场景

内容的提问来源于stack exchange，提问作者user1621001