Использование бинарных деревьев для поиска анаграмм

Question

В настоящее время я пытаюсь создать метод, который использует двоичное дерево, которое находит анаграммы слова, введенного пользователем.

Если дерево не содержит никакой другой анаграммы для слова (т. Е. Еслиключ не был в дереве, или единственным элементом в связанном связанном списке было слово, предоставленное пользователем), печатается сообщение «анаграмма не найдена» Например, если в дереве появляется ключ «opst» со связанным связанным спискомсодержащий слова «spot», «pots» и «tops», а пользователь дал слово «spot», программа должна вывести «pots» и «tops» (но не spot).

public boolean find(K thisKey, T thisElement){
    return find(root, thisKey, thisElement);
}

public boolean find(Node current, K thisKey, T thisElement){
    if (current == null)
        return false;
    else{
        int comp = current.key.compareTo(thisKey);
        if (comp>0)
            return find(current.left, thisKey, thisElement);
        else if(comp<0)
            return find(current.right, thisKey, thisElement);
        else{
            return current.item.find(thisElement);
        }
    }
}

Когда я создал этот метод, чтобы определить, находится ли предоставленный элемент в дереве (и связанном ключе), мне сказали не использовать этот код для поиска анаграмм.

K - это универсальный тип, расширяющий Comparableи представляет Ключ, T - универсальный тип, представляющий элемент в списке.

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

Answer 1

Немного неясно, что именно вас подстерегает (кроме того, что «я написал хороший метод поиска, но мне не разрешено его использовать»), поэтому я думаю, что лучше всего начать с самого начала.

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

У вас есть три вещи:

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

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

3) Введенная пользователем строка.

Понимание : анаграммы группы букв образуют класс эквивалентности .Это означает, что любой член списка анаграмм может использоваться в качестве ключа, связанного со списком.Кроме того, это означает, что вам не нужно хранить в своем дереве несколько ключей, которые указывают на один и тот же список (при условии, что мы немного сообразительны в отношении структурирования наших данных; см. Ниже).

В конкретных терминах, нет необходимости использовать и «spot», и «opts» в качестве ключей в дереве, указывающих на один и тот же список, потому что, как только вы сможете найти список, используя любую анаграмму «spot»,вы получаете все анаграммы "пятна".

Умное структурирование ваших данных : Учитывая наше понимание, предположим, что наше дерево содержит ровно один ключ для каждого уникального набораанаграммы.Таким образом, "opts" отображается на {"opts", "pots", "spot" и т. Д.}.Что произойдет, если наш пользователь даст нам строку, которую мы не используем в качестве ключа для своего набора анаграмм?Как мы можем выяснить, что если пользователь вводит «spot», мы должны найти список с ключом «opts»?

Ответ заключается в нормализации данных, хранящихся в наших данныхструктур.Это компьютерный способ сказать, что мы применяем произвольные правила хранения данных.(Нормализация данных - это полезный метод, который неоднократно встречается во многих различных областях компьютерной науки.) Первое правило заключается в том, что в нашем дереве только ОДИН ключ, который отображается в данный связанный список.Во-вторых, что если мы удостоверимся, что каждый ключ, который мы на самом деле храним, предсказуем - то есть мы знаем, что нам следует искать «опции», даже если пользователь вводит «спот»?

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

Помещение в неговместе : я приведу здесь высокоуровневый алгоритм, чтобы сделать это немного более конкретным.

1) Получите строку от пользователя (держитесь за эту строку, она понадобится нам позже)

2) Превратить эту строку в ключ поиска, который следует нашей схеме нормализации (Вы можете сделать это в конструкторе вашего класса "K", который гарантирует, что у вас никогда не будет ненормализованного ключа где-нибудь в вашей программе .)

3) Найдите дерево для этого ключа и получите связанный список, связанный с ним.Этот список содержит каждую анаграмму входной строки пользователя.

4) Печатает каждый элемент в списке, который не исходная строка пользователя (посмотрите, почему мы сохранили эту строку под рукой?)

---

Еда на вынос :

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

Нормализация ваших данных обеспечивает предсказуемость и позволяет эффективно рассуждать об этом. Насколько сложнее будет алгоритм «поиска», если каждый ключ может быть произвольным членом своего списка анаграмм?

Следствие: Получение правильных структур данных (что я храню? Как связаны части? Как они представлены?) Значительно упростит написание ваших алгоритмов.

Answer 2

Как насчет сортировки символов в словах, а затем сравнить это.