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

Question

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

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

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

Answer 1

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

-Adam

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

Хорошо Сортируйте слова в списке.

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

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

Answer 6

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

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

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

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

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

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

Answer 10

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