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

Question

当你构建一个 trie 时，你是否将字符串/句子存储在其分支的末尾以便于在分支的末尾访问它？有些人这样做，我有时也这样做，但我应该这样做吗？

有时（尤其是 LeetCode），我会得到这个错误：

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

这个错误只是意味着我已经超出了我的深度优先搜索函数的调用堆栈。

除了我的 Trie class:

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 class 只是从 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);
    }
}

（顺便说一句，将字符串存储为结束标记本身并没有什么坏处。您通常可以从通过特里树的路径构建单词，但考虑存储 [=15= 的数字的特里树], 您可能希望在结束节点处存储有效单词列表。）

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

Trie storing string at the end of branch exceeds call stack limit

javascript

algorithm

trie