时间戳

首页 > 解决方案 > 我有一个关于该功能如何工作的问题

javascript - 我有一个关于该功能如何工作的问题

问题描述

在求解算法时，有一部分我不明白该函数的工作原理。

function letterCombinations(digits) {
    var map = ['0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    var res = [];
    var prefix = [];

    if (digits.length) {
        traverse(0);
    }
    return res;

    function traverse(idx) {
        if (idx === digits.length) {
            return res.push(prefix.join(''));
        }

        var str = map[digits[idx] - '0'];

        for (var i = 0; i < str.length; i++) {
            prefix.push(str[i]);
            traverse(idx + 1);
            prefix.pop();
        }
    }
}

当遇到遍历函数内部的条件语句时

 if (idx === digits.length) {
        return res.push(prefix.join(''));
    }

为什么pop方法没有退出函数就执行了？

prefix.pop()

标签： javascriptalgorithmrecursion

解决方案

你的措辞有点模棱两可，但我想明白你真正要问的。

是函数内部的一行，递归prefix.pop()调用自身。traverse()traverse()

以letterCombinations('23')对应的地方str为例2: 'abc', 3: 'def'。该过程可以可视化为以下伪代码：

traverse(0)
  i=0, push('a') // prefix=['a']

  traverse(1)
    loop when i=0:
      push('d')       // prefix=['a', 'd']
      traverse(2)     // since `2==digits.length`, it's a short-circuit return
                      // no `pop()` called inside `traverse(2)`
      pop_1() -> 'd'  // prefix=['a']
    
    loop when i=1:
      push('e')       // prefix=['a', 'e']
      traverse(2)     // short-circuit return
      pop_1() -> 'e'  // prefix=['a']

    loop when i=3:
      ...
    
  pop_0()

您会感到困惑，因为您将注意力集中在prefix.pop()中的代码行上，在伪代码中traverse(0)标记为。pop_0()但是您忘记了跟踪递归。

发挥您的想象力并踏入traverse(1)，您会在prefix.pop()那里找到另一个呼叫，标记为pop_1()。

所以回答你的问题：

为什么pop方法没有退出函数就执行了？

你说得对，我们还没有退出traverse(0)，但是 pop 方法实际上是在里面调用的traverse(1)。traverse(2)在那里，由于短路返回，我们已经退出。

推荐阅读