Co to jest łatwy sposób stwierdzić, czy lista słów jest wzajemnie anagramowa?

Question

W jaki sposób wymieniasz słowa, które są wzajemnie anagramami?

Zostałem poproszony o to pytanie, gdy ubiegałem się o moją obecną pracę.

może być zmieniony na carthorse z wszystkimi oryginalnymi literami używanymi dokładnie jeden raz dlatego słowa są anagramami od siebie.

Answer 1

Umieść wszystkie litery w kolejności alfabetycznej w ciągu znaków (algorytm sortowania), a następnie porównaj wynikowy ciąg.

-Adam

Answer 2

Sortowanie każdego elementu (usuwanie białych znaków) i porównywanie z poprzednim. Jeśli wszystkie są takie same, wszystkie są anagramami.

Answer 3

Sortuj litery i porównać (litera po literze, ciąg porównania, ...) to pierwsze rzeczy, które przychodzi do głowy.

Answer 4

Poniższy algorytm powinien działać:

1. posortować litery każdego słowa.

2. Posortuj posortowane listy liter na każdej liście.

3. Porównaj każdy element na każdej liście pod kątem równości.

Answer 5

Co ciekawe, Eric Lippert's Fabulous Adventures In Coding Blog czynienia z odmianą tego samego problemu w dniu 4 lutego 2009 roku w this post.

Answer 6

Dobrze, że wszyscy żyjemy w rzeczywistości C# w miejscu sortowania krótkich słów na maszynach czterordzeniowych z jazami pamięci. :-)

Jeśli jednak masz ograniczoną pamięć i nie możesz dotknąć oryginalnych danych i wiesz, że te słowa zawierają znaki z dolnej połowy tabeli ASCII, możesz wybrać inny algorytm, który się liczy występowanie każdej litery w każdym słowie zamiast sortowania.

Możesz także wybrać ten algorytm, jeśli chcesz zrobić to w trybie O (N) i nie obchodzi go użycie pamięci (licznik każdego znaku Unicode może być dość kosztowny).

Answer 7

1. porównać długość (jeśli nie równy, a nie przypadkowo)
2. dokonać bitowy wektor długości strun
3. dla każdego char w pierwszym ciągiem znaleźć wystąpienia niego w drugim
4. ustawić bit dla pierwszego wyłączonym wystąpienia
5. jeśli można znaleźć jeden przystanek z funkcją

Answer 8

Dobrze Sortowanie słów na liście.

jeśli abc, bca, cab, cba są wejściami, to posortowana lista będzie abc, abc, abc, abc.

Teraz wszystkie ich kody są równe.Porównaj HashCodes.

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

Tried logika hashcode dla anagram daje mi fałszywe wyjście

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 
    } 

naprawić ten kod, poniżej jest jedyną opcją, widzę, doceniam wszelkie zalecenia

char[] ch1 = s.toLowerCase().toCharArray(); 
     Arrays.sort(ch1); 
     char[] ch2= s2.toLowerCase().toCharArray(); 
     Arrays.sort(ch2); 
     return Arrays.equals(ch1,ch2); 
    }