Tr ie строка хранения в конце ветви превышает предел стека вызовов

Question

Когда вы строите tr ie, сохраняете ли вы строку / предложение в конце его ветви, чтобы легко получить к нему доступ в конце ветви? Некоторые люди делают, и я иногда, но я должен?

Иногда (особенно с LeetCode), я получаю эту ошибку:

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

Ошибка просто означает, что я превысил стек вызовов для моя функция поиска в глубину.

Я ничего не изменил, кроме своего класса Tr ie:

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

Класс Tr ie просто строит tr ie из string[]: sentences и я больше ничего не делаю с символом конца #, поэтому другой ошибки нет.

Answer 1

Вы отмечаете конец слова, сохраняя специальный дозорный ключ '#' в объектах, составляющих узлы вашего дерева. Значения, связанные с ключами, являются узлами-потомками для следующей буквы, но значение, связанное с ключом часового типа, является строкой.

При поиске в глубину вы перебираете все ключи в узле, и если ключ - страж, вы добавляете слово, которое вы создали до сих пор. Но затем вы также возвращаете ключ дозорного и передаете строку как новый root узел. В следующей рекурсии l oop

for (const key in root) ...

перебирает символы строки, которая перечисляет ее символы:

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

Следующая рекурсия будет перебирать символы, то есть над однобуквенными строками. И так далее. Чрезмерная рекурсия не исходит от tr ie, но когда вы случайно покинете tr ie и вернетесь в строки.

Если вы используете true в качестве значения для сторожевого ключа, есть перебирать нечего, поэтому проблема не возникает.

Решение состоит в том, чтобы выполнять рекурсию только в том случае, если ключ не является стражем:

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

(Кстати, нет ничего плохого в сохранении строки как конечного маркера как таковой. Обычно можно составить слово из пути через tr ie, но рассмотрим tr ie, в котором хранятся цифры словаря T9 где вы можете сохранить список допустимых слов в конечных узлах.)