Написал метод который находит все анаграммы из списка переданных слов. В котором первым шагом - я просто фильтрую по длине слова, второй шаг это - фильтрация по чексумме которую я вычисляю просто суммирую все chars
, третий этап это уже точная проверка, в массиве (indexes) хранится количество каждой буквы подскажите что можно улучшить в этом алгоритме или может я вообще не тем путем иду и есть что то быстрее?
-
@anton-sorokin для вашего предыдущего ответа если initalString = "ksmk" и добавить в массив слово "mskk" он не найдет это слово – J Mas 25 фев '19 в 13:25
-
Все, понял. Я думал, что анаграмма - это когда слово написано в обратно порядке. – Anton Sorokin 25 фев '19 в 15:17
-
Список слов постоянный, а word меняется, так? – MBo 26 фев '19 в 8:33
-
@Mbo И то и другое не постоянное – J Mas 26 фев '19 в 13:00
-
т.е. каждый раз передаётся список слов и одно слово, к которому в списке нужно найти анаграммы? – MBo 26 фев '19 в 14:15
|
показать ещё 1 комментарий
2 ответа
Для сравнения слова с одноразовым списком нет смысла разбивать на несколько стадий.
Отсортировать буквы слова word => dorw
Перебирать слова списка по порядку, смотреть длину, если совпадает - отсортировать буквы, сравнить с искомым словом.
-
Сама сортировка займет много времени, а тут еще и сравнение делать, как это мжоет быть быстрее моего варианта – J Mas 26 фев '19 в 20:30
-
Сортировка символов в слове (не слов между собой) - очень быстрая. Собственно, Anton Sorokin уже реализовал этот метод, стоит попробовать. Могу даже предположить, что больше времени уйдёт на преобразование слов в CharArray, чем на саму сортировку – MBo 27 фев '19 в 3:29
-
String это и есть char[], он просто возвращает этот используемый массив. А если использовать charAt то он вовсе не копирует. – J Mas 27 фев '19 в 9:03
-
Только вот String в джаве неизменяемый, поэтому для сортировки символов в слове приходится создавать новый объект другого типа, содержащий копию тела строки – MBo 27 фев '19 в 9:06
-
Вот код:
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]);
}
-
@JMas: ну что, есть какие-то замечания? И по поводу вопроса с замером скорости. – Anton Sorokin 26 фев '19 в 16:09
-
Сортировка занимает много времени, из миллиона слов мне придется отсортировать 10 000 слов, и это не будет быстро – J Mas 26 фев '19 в 19:30
-
-
Сортировка как минимум log n, сортировка плюс сравнение, в момем случае я сразу сравниваю charы – J Mas 27 фев '19 в 9:06
-