Как бы вы перечислили слова, которые являются анаграммами друг друга?Что такое простой способ сказать, является ли список слов анаграммами друг друга?
Мне задали этот вопрос, когда я подал заявку на свою текущую работу.
orchestra может быть перестроен в carthorse со всеми оригинальными буквами, используемыми ровно один раз, поэтому слова являются анаграммами друг друга.
Поместите все буквы в алфавитном порядке в строку (алгоритм сортировки), а затем сравните полученную строку.
-Adam
Да, это в значительной степени то, что я придумал ... Получил задание! – jqs
Существует альтернативный алгоритм, включающий подсчет символов в каждом слове. Это быстрее, но для юникодовых слов это будет дороже. –
Я подумал об этом, но тогда вам нужно сравнить полученные массивы счетчиков, хэши или иначе - для коротких анаграмм мой алгоритм, скорее всего, быстрее, но для больших анаграмм шансы хорошие, ваши будут быстрее. Было бы интересным тестом ... –
Сортировка каждого элемента (удаление пробелов) и сравнение с предыдущим. Если они все одинаковые, они все анаграммы.
Удаление знаков препинания также – dmckee
пунктуация Я могу понять, для слов с апострофе, но пространства? Я не знаю много слов с пробелами в них ... Я думаю, что для простого упражнения, подобного этому, можно смело предположить, что слова содержат только буквы. – ninesided
Когда представлены в виде головоломок, анаграммы часто распространяются на целые фразы. Поэтому вы пишете рутину, чтобы быть надежной. – dmckee
Сортировать буквы и сравнивать (по буквам, строка сравнения, ...) это первое, что приходит на ум.
Следующий алгоритм должен работать:
Сортировать буквы в каждом слове.
Сортировка отсортированных списков букв в каждом списке.
Сравните каждый элемент в каждом списке для равенства.
После сортировки списков букв вы можете сравнить первое и последнее, а не сравнивать их. Если первое совпадает с последним, то все они равны. –
@EricNess Вы в этом уверены? Рассмотрим ввод: «abbc» и «abcc». Такая же длина, одни и те же первые и последние персонажи ... Или, может быть, я неправильно понял ваш комментарий. – levigroker
Интересно, что Eric Lippert's Fabulous Adventures In Coding Blog имел дело с вариацией по этой проблеме на 4 февраля 2009 года в this post.
Хорошо, что все мы живем в реальности C# на месте сортировки коротких слов на четырехъядерных машинах с ооглядами памяти. :-)
Однако, если вы случайно ограничены памятью и не можете коснуться исходных данных, и вы знаете, что эти слова содержат символы из нижней половины таблицы ASCII, вы можете пойти по другому алгоритму, который учитывает появление каждой буквы в каждом слове вместо сортировки.
Вы также можете выбрать этот алгоритм, если хотите сделать это в O (N), и не заботитесь об использовании памяти (счетчик для каждого символа Unicode может быть довольно дорогим).
char в первой строке найти вхождения его в второйНу Отсортировать слова в списке.
, если abc, bca, cab, cba - входы, тогда отсортированный список будет abc, abc, abc, abc.
сейчас все их хэш-коды равные.Сравните HashCodes.
public static void main(String[] args) {
String s= "abc";
String s1="cba";
char[] aArr = s.toLowerCase().toCharArray();
char[] bArr = s1.toLowerCase().toCharArray();
// An array to hold the number of occurrences of each character
int[] counts = new int[26];
for (int i = 0; i < aArr.length; i++){
counts[aArr[i]-97]++; // Increment the count of the character at respective position
counts[bArr[i]-97]--; // Decrement the count of the character at respective position
}
// If the strings are anagrams, then counts array will be full of zeros not otherwise
for (int i = 0; i<26; i++){
if (counts[i] != 0)
return false;
}
Пробовал хэш логика анаграммы дает мне ложные выходные
public static Boolean anagramLogic(String s,String s2){
char[] ch1 = s.toLowerCase().toCharArray();
Arrays.sort(ch1);
char[] ch2= s2.toLowerCase().toCharArray();
Arrays.sort(ch2);
return ch1.toString().hashCode()==ch2.toString().hashCode(); //wrong
}
исправить этот код, ниже это единственный вариант, я вижу, оценить какие-либо рекомендации
char[] ch1 = s.toLowerCase().toCharArray();
Arrays.sort(ch1);
char[] ch2= s2.toLowerCase().toCharArray();
Arrays.sort(ch2);
return Arrays.equals(ch1,ch2);
}
Эй! Мы задаем этот вопрос каждому программисту, с которым мы беседуем! Ты портишь вещи для нас! –
@Jim В Техасе: вопрос не портит вашу стратегию интервью, он показывает, что стратегия интервью будет в корне ошибочной. Как собирать механика, исходя из того, какие цвета он имеет. Утечка знаний новым кандидатам, которые вы всегда выбираете синим комбинезоном, не портит вашу стратегию выбора механиков. Он раскрывает это как нестратегию как недостаток того, что ее могут нарушить люди, не знающие программирования. –
Мне сложно изобразить «людей без знания программирования», которые могут встать на белой доске и написать программу для обнаружения анаграмм. На самом деле это действительно отличный начальный экранный вопрос по многим причинам. И действительно, если кандидат заинтересован достаточно, чтобы прочитать этот вопрос, тогда это хорошо! –