Самый быстрый способ найти все аннаграммы

117

26 октября 2019, 05:30

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

Answer 1

Для сравнения слова с одноразовым списком нет смысла разбивать на несколько стадий.

Отсортировать буквы слова word => dorw

Перебирать слова списка по порядку, смотреть длину, если совпадает - отсортировать буквы, сравнить с искомым словом.

Answer 2

Вот код:

    String[] stringArray = {"weddw", "cew", "ghr", "kov", "wev"};
    String initialWord = "wce";
    char[] word = initialWord.toCharArray();
    Arrays.sort(word);
    char[] secondWord;
    for (int i = 0; i < stringArray.length; i++)
        if(initialWord.length() == stringArray[i].length()) {
            secondWord = stringArray[i].toCharArray();
            Arrays.sort(secondWord);
            if(Arrays.equals(word, secondWord))
                System.out.println(stringArray[i]);
        }