Почему этот итерационный обход не дает правильного слова при запросе? - PullRequest
Новая
       39

Почему этот итерационный обход не дает правильного слова при запросе?

0 голосов
/ 01 февраля 2019

Итак, вот мое затруднительное положение: я пытаюсь пройти через структуру данных три, чтобы найти n-е слово.

Для тех из вас, кто не знаком, trie - это структура данных на основе сжатия, которая позволяет вставлять серии слов и сортировать их лексикографически, но каждый узел должен иметь свою собственную отдельную букву и, таким образом, разветвлятьсяи написание соответствующих слов (если неясно, кто-то, у кого есть более конкретное определение, пожалуйста, исправьте!).

Каждый узел в дереве имеет массив из 26 узлов, представляющих 26 букв алфавита.Как только слово написано, логическое значение в массиве (isWord) для последнего символа в слове помечается как true.Это также относится к словам в словах, таких как {a, and, are, art};«A» - это слово, поэтому isWord для этой буквы установлено в true.Однако буквы внутри «и» прикрепляются к «а», а «d» помечается как слово.

Теперь, когда введение установлено, вот моя проблема: мне очень трудно сделать это рекурсивно, поэтому я попытался сделать это итеративно.Я очень, очень близок к решению, но по какой-то причине некоторые слова пропускаются, когда я вызываю nthWord (int n).По сути, метод должен проходить по дереву (которое в алфавитном порядке по свойству дерева) и находить n-е слово, как следует из названия.Но, как было сказано выше, иногда метод пропускает слова в дереве, даже если он гарантированно добавляется в дерево (и логическое значение isWord также всегда корректно).Я был в этой проблеме около 3 дней, и я так потерян.

Я ожидаю, что выводом будет n-е слово в последовательности (из очень большого .txt файла слов), но иногда оно пропускает определенные слова.Если j присвоено -1, учитываются такие слова, как «aardvark», которые начинаются с 2 одинаковых букв, но другие пропускаются.И наоборот, если ему присвоено значение 0, учитываются другие слова, но слова, начинающиеся с двух одинаковых букв, пропускаются.

РЕДАКТИРОВАТЬ: я должен также указать, что метод nthWord (...) не 'Обрабатывать повторяющиеся слова.Три хранит частоты каждого слова в последнем символе указанного слова.Поэтому повторяющиеся слова не являются проблемой в этом случае.

1 Ответ

0 голосов
/ 01 февраля 2019

Вот рекурсивное решение этого вопроса (которое более интуитивно понятно).Просто отнеситесь к этому как к проблеме дерева, когда вам нужно пройтись по дереву слева направо и попытаться найти N -ое слово.

Вы можете DFS из корневого узла.Сохраните переменную для хранения количества слов, которые вы посетили до сих пор (количество узлов с isWord, которые вы посетили).И верните слово, когда достигнете N -го слова.

Код будет примерно таким.Я только что написал код шаблона - 

def findWord(TrieNode,word):
    global N
    if TrieNode.isWord:
        if N == 0:
            return word
        else:
            N -= 1

    for each in TrieNode.children:
        if each is not None:
            word += each.character
            res = findWord(N,each,word)
            if len(res) > 0:
                return res
            word = word[:-1]
    return ''
N = input()
findWord(root,'')
...