Какой простой способ определить, являются ли списки слов анаграммами друг друга?

Question

Как бы вы перечислили слова, которые являются анаграммами друг друга?

Мне задали этот вопрос, когда я подал заявку на мою текущую работу.

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

Answer 1

Поместите все буквы в алфавитном порядке в строке (алгоритм сортировки), а затем сравните полученную строку.

-Адам

Answer 2

Хорошо, что все мы живем в реальности C# сортировки коротких слов на местах на четырехъядерных компьютерах с множеством памяти.:-)

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

Вы также можете выбрать этот алгоритм, если вы хотите сделать это в O(N) и не заботиться об использовании памяти (счетчик для каждого символа Unicode может быть довольно дорогим).

Answer 3

Сортировка каждого элемента (удаление пробелов) и сравнение с предыдущим. Если они все одинаковы, они все анаграммы.

Answer 4

Интересно, что в этом посте Эрик Липперт "Потрясающие приключения в коде" описал вариант этой проблемы 4 февраля 2009 года.

Answer 5

Следующий алгоритм должен работать:

1. Сортировка букв в каждом слове.

2. Сортировать отсортированные списки букв в каждом списке.

3. Сравните каждый элемент в каждом списке на равенство.

Answer 6

Ну сортируйте слова в списке.

если abc, bca, cab, cba являются входными данными, то отсортированным списком будет abc, abc, abc, abc.

Теперь все их хэш-коды равны. Сравните хэш-коды.

Answer 7

Сортировка букв и сравнение (буква за буквой, сравнение строк, ...) - это первое, что приходит на ум.

Answer 8

Пробная логика хеш-кода для анаграммы дает мне ложный вывод

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);
    }

Answer 9

1. сравнить длину (если не равны, не случайно)
2. сделать битовый вектор длины строк
3. для каждого char в первой строке найдите его появления во второй
4. установить бит для первого неустановленного вхождения
5. если вы можете найти одну остановку с ошибкой

Answer 10

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;
  }