Лучшего алгоритм поиск анаграммы слова из справочника

Question

Я получил проблемы что-то вроде этого

У меня есть список, который является словарем, содержащий миллионы слов, и я дал вход слово как OSPT onlt-слова могут быть сформированы STOP и POST .. Я хочу, чтобы узнать все слова анаграмм, соответствующие в dictonary оптимизированным образом.

Что я решил.

я дал ниже solution.I будет взять слово и переставить его и проверить слово есть в словаре или not.But это п * п не optimized.Is Есть ли способ решить эту проблему

Answer 1

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

Когда вам дается слово для поиска анаграмм, вы сортируете символы в этом слове по алфавиту и выполняете поиск на карте.

Из вашего примера и добавляя слово БАССЕЙН, вы получите:

LOOP -> [LOOP, POOL, POLO] 
OPST -> [STOP, POST] 

код Java будет что-то вроде:

public class AnagramGenerator 
{ 
    private Map<String, Collection<String>> indexedDictionary; 

    public AnagramGenerator(List<String> dictionary) 
    { 
    this.indexedDictionary = index(dictionary); 
    } 

    public Collection<String> getAnagrams(String word) 
    { 
    return indexedDictionary.get(sort(word)); 
    } 


    private Map<String, Collection<String>> index(List<String> dictionary) 
    { 
    MultiMap<String, String> indexedDictionary = HashMultimap.create(); 

    for (String word : dictionary) 
    { 
     indexDictionary.put(sort(word), word); 
    } 

    return indexedDictionary.asMap(); 
    } 

    private String sort(String word) 
    { 
    List<Character> sortedCharacters= Arrays.asList(word.toCharArray()); 
    Collections.sort(sortedCharacters); 

    StringBuilder builder = new StringBuilder(); 
    for (Character character : sortedCharacters) 
    { 
     builder.append(character); 
    } 

    return builder.toString(); 
    } 
} 

Answer 2

Вы можете сделать это.

• Сортируйте каждое слово и добавьте его в MultiMap отсортированного слова к текущему слову.
• Посмотрите каждое слово, чтобы использовать его в качестве анаграммы, сначала отсортировав слово.

Стоимость индекса один раз и O (N), где N - количество слов.

После этого стоимость сортировки - это O (M log M) для сортировки букв, где M - количество букв. Это очень дешево по сравнению со стоимостью расчета перестановок.

BTW Этот подход, слова сканируются только один раз, заранее.

Answer 3

Это может быть сделано следующим образом:

Для данного слова, сохранить количество всех символов в нем. Например, для OSTP,

count['O'] = 1; 
count['S'] = 1; 
count['T'] = 1; 
count['P'] = 1; 

Вы можете создать массив из 26 элементов, подобных этому.

Затем, итерации через словарь, просто проверьте, какое слово имеет одинаковое количество символов.

Answer 4

Вы можете Preprocess список: заменить любое слово из он с его отсортированной анаграммой (т.е. абакаба становится aaaabbc). Эта строка однозначно представляет любое слово, которое является анаграммой слова из словаря.

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

Answer 5

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

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

Смотрите также здесь взаимосвязанного решения в с - Generate same unique hash code for all anagrams