Anagram - wykrywanie i grupowanie

1. Czym jest anagram?

Anagram to słowo lub fraza utworzona przez przestawienie liter innego słowa lub frazy, używając wszystkich oryginalnych liter dokładnie raz.

Przykłady:

✅ Anagramy słów:
- "listen" ↔ "silent"
- "evil" ↔ "vile" ↔ "live"
- "heart" ↔ "earth"
- "stressed" ↔ "desserts"

✅ Anagramy fraz (ignorując spacje):
- "astronomer" ↔ "moon starer"
- "the eyes" ↔ "they see"

❌ NIE anagramy:
- "hello" i "world" (różne litery)
- "abc" i "abcd" (różna długość)

2. Wykrywanie anagramów - sortowanie

2.1. Najprostsze podejście:

Złożoność: - Czasowa: O(n log n) – sortowanie - Pamięciowa: O(n) – nowe listy

3. Wykrywanie anagramów - liczenie znaków

3.1. Używając słownika:

Złożoność: - Czasowa: O(n) ✅ - Pamięciowa: O(k) – k = liczba unikalnych znaków

3.2. Używając Counter:

Najkrótsza i najczytelniejsza wersja! ✅

4. Wykrywanie anagramów - tablica znaków

4.1. Dla alfabetu ASCII:

Zalety: - O(n) czas - O(1) pamięć (zawsze 26 elementów) ✅

5. Anagramy ignorując wielkość liter i spacje

6. Grupowanie anagramów

6.1. Problem:

Dany lista słów, zgrupuj anagramy razem.

6.2. Rozwiązanie – sortowanie jako klucz:

6.3. Rozwiązanie – liczenie jako klucz:

Złożoność: O(n × k) – lepsza niż sortowanie! ✅

7. Znajdowanie wszystkich anagramów w tekście

7.1. Problem:

Znajdź wszystkie indeksy startowe anagramów pattern w text.

7.2. Rozwiązanie – sliding window:

Złożoność: O(n) – każdy znak przetwarzany raz! ✅

8. Najdłuższy anagram w słowniku

9. Sprawdzanie, czy string zawiera anagram podstringa

10. Minimalne okno zawierające anagram

Złożoność: O(n + m)

11. Permutacje anagramów

Złożoność: O(n! × n) – eksponencjalna!

12. Porównanie metod wykrywania anagramów

13. Anagramy w praktyce

13.1. Gry słowne:

13.2. Sprawdzanie nazw użytkownika:

14. Podsumowanie

Anagram:

  • Słowo/fraza utworzona przez przestawienie liter
  • Przykłady: "listen" ↔ "silent", "evil" ↔ "vile"

Metody wykrywania:

Metoda Czas Pamięć Zalety
Sortowanie O(n log n) O(n) Najprostsza
Counter O(n) ✅ O(k) Czytelna, pythoniczne
Tablica (a-z) O(n) ✅ O(1) ✅ Najszybsza (tylko małe litery)
Słownik O(n) O(k) Uniwersalna

Implementacje podstawowe:

Grupowanie anagramów:

Sliding window dla anagramów w tekście:

Kluczowe obserwacje:

  • Anagramy mają tę samą długość – sprawdź to najpierw!
  • Sortowanie jako klucz – prosty sposób na grupowanie
  • Counter w Pythonie – najbardziej czytelne rozwiązanie
  • Sliding window – O(n) dla znajdowania w tekście

Zastosowania:

  • Gry słowne (Scrabble, krzyżówki)
  • Wykrywanie podobnych nazw (phishing)
  • Bezpieczeństwo (hasła podobne do loginów)
  • Bioinformatyka (podobne sekwencje)
  • Wyszukiwarki (sugestie słów)

Co dalej warto poznać:

  • Wyszukiwanie wzorców – Rabin-Karp, KMP
  • Permutacje i kombinacje – generowanie anagramów
  • Hash functions – szybkie porównywanie
  • Trie structures – grupowanie słów
  • Edit distance – podobieństwo stringów (Levenshtein)
Wróć do spisu lekcji