Trie在分支末尾存储的字符串超出了调用堆栈限制

Question

构建特里树时，是否将字符串/句子存储在其分支的末尾以方便在分支的末尾进行访问？有些人会做，有时我会做，但是我应该吗？

有时（尤其是使用LeetCode），出现此错误：

Line # in solution.js
AutocompleteSystem.prototype.dfs = function(root, char, foundStrings) {
                                           ^
RangeError: Maximum call stack size exceeded

错误仅表示我的深度优先搜索功能超出了调用堆栈。

除了我的Trie课外，我没有其他改变：

class Trie {
    constructor() {
        this.root = {};
        this.end = '#';
    }

    insert(sentence, times) {
        let current = this.root;
        for (const char of sentence) {
            if (current[char] == null) {
                current[char] = {};
            }
            current = current[char];
        }
        current[this.end] = true; // This works fine, submission accepted.
        // If I store the string here like so:
        // current[this.end] = sentence; I get the error.
        current.times = current.times + 1 || times;
    }
}

// As you can see, the dfs function won't affect 
// if I store the string at the end of each branch or not 
// because it doesn't use the value of #
const dfs = function(root, char, foundStrings) {
    for (const key in root) {
        // If reach the end of a branch:
        if (key === '#') {
            // If the current times not already in foundStrings:
            if (!foundStrings[root.times]) {
                // Initiate an empty array with the new times as key
                // to store strings later:
                foundStrings[root.times] = [];
            }
            // Else, push the found string into foundStrings, grouped by times:
            foundStrings[root.times].push(char);
            // Sort all strings in the same group:
            foundStrings[root.times].sort();
        }
        // Keep searching:
        this.dfs(root[key], char + key, foundStrings);
    }
}

Trie类只是从string[]: sentences构建一个trie，而我对结束符号#不做任何其他操作，因此没有其他错误。

Answer 1

您通过在构成树节点的对象中存储特殊的前哨键'#'来标记单词的结尾。与这些键关联的值是下一个字母的后代节点，但与前哨键关联的值是一个字符串。

在深度优先搜索中，您迭代节点中的所有键，如果键是哨兵，则添加到目前为止已构建的单词。但是随后，您还向下递归了前哨键，并将字符串作为新的根节点传递。在下一个递归中，循环

for (const key in root) ...

迭代字符串的字符，该字符串枚举其字符：

{0: 't', 1: 'r', 2: 'i', 3: 'e'}

下一次递归将遍历字符，即遍历单字母字符串。依此类推。过度的递归不是来自trie，而是当您不小心离开了trie并递归为字符串时。

如果仅使用true作为前哨键的值，则没有要迭代的内容，因此不会出现问题。

解决方案是仅在密钥不是前哨时才递归：

for (const key in root) {
    if (key === '#') {
        // add found string to list ...
    } else {
        this.dfs(root[key], char + key, foundStrings);
    }
}

<