Использование двоичных деревьев для поиска Anagrams

Question

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

Если дерево не содержит никакой другой анаграммы для слова (т. Е. Если ключ не был в дереве или единственным элементом связанного списка было слово, предоставленное пользователем), сообщение «no anagram found "печатается Например, если в дереве появляется ключ« opst »со связанным списком, содержащим слова« 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) Строка, введенная пользователем.

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

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

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

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

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

Объединение: Здесь я предоставлю алгоритм высокого уровня, чтобы сделать это немного более конкретным.

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

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

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

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

---

Takeaways:

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

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

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

Answer 2

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