Znajdowanie anagramów dla danego słowa
Dwa słowa są anagramami, jeśli jedno z nich ma dokładnie takie same znaki, jak inne słowo.
Przykład:Anagram
& Nagaram
są anagramami (bez rozróżniania wielkości liter).
Teraz jest wiele pytań podobnych do tego. Kilka podejść do ustalenia, czy dwa łańcuchy są anagramami to:
1) Sort
sznurki i porównaj je.
2) Stwórzfrequency map
dla tych ciągów i sprawdź, czy są takie same lub nie.
Ale w tym przypadku otrzymujemy słowo (dla uproszczenia załóżmy tylko jedno słowo i będzie ono miało tylko pojedyncze anagramy słów) i musimy w tym celu znaleźć anagramy.
Rozwiązanie, które mam na myśli, jest takie, że możemygeneruj wszystkie permutacje za słowo i sprawdź, które z tych słówistnieje w słowniku . Ale oczywiście jest to bardzo nieefektywne. Tak, słownik jest również dostępny.
Jakie mamy alternatywy?
Czytam również w podobnym wątku, że można coś zrobić za pomocąTries
ale osoba nie wyjaśniła co to był algorytm i dlaczego użyliśmy Trie na pierwszym miejscu, tylko implementacja została dostarczona również w Pythonie lub Rubim. Więc to nie było naprawdę pomocne, dlatego stworzyłem nowy wątek. Jeśli ktoś chce udostępnić swoją implementację (inną niż C, C ++ lub Java), to również proszę to wyjaśnić.