Как перейти Tr ie Узел в структуре данных Tr ie? - PullRequest
Новая
       92

Как перейти Tr ie Узел в структуре данных Tr ie?

0 голосов
/ 28 апреля 2020

Я пытаюсь использовать Tr ie для решения следующей проблемы. Давайте рассмотрим эти строки для вставки в Tr ie: 

String s1 = "Elephant";
String s2 = "Alfphant";
String s3 = "Ilophnit";

Я хотел бы знать, есть ли хотя бы одна строка, содержащая символы: ' l ' в вторая позиция, ' h ' в пятой позиции и ' n ' в шестой позиции.

Я использую простой Tr ie реализации , и моя цель - получить эффективное исследование с использованием Tr ie. Это предлагаемая функция: 

    boolean containsNode(String word) {
        TrieNode current = root;
        TrieNode node = null;

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);

            node = current.getChildren().get(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return current.isEndOfWord();
    }

Предполагая, что я знаю, какие символы нужно найти и их позиции, я подумал о создании прыжка в итерациях. Однако, таким образом, сложность поиска возрастает, потому что я должен рассмотреть все дочерние элементы каждого узла.

У вас есть какие-нибудь решения для меня? Существуют ли другие типы Tr ie, Tree или структур данных, которые могут эффективно решить мою проблему?

...