Strona główna » Algorytmy » Artykuły » Wyrażenia w Anagramy
 

Wyrażenia w Anagramy

https://mattomatti.com/a0181

Zadanie

Dane są dwa wyrażenia złożone z małych liter alfabetu łacińskiego. Ile znaków trzeba usunąć w obydwu wyrażeniach, aby były anagramami? Zakładamy, że jest to możliwe bez usuwania wszystkich znaków.

Przykładowo dla słów "abcd" oraz "abc" trzeba usunąć 1 znak (literę "d"). Z kolei dla wyrażeń "zegar" oraz "gracz" trzeba usunąć łącznie 2 znaki. Są to odpowiednio litery "e" oraz "c".

Analiza zadania

Zadanie sprowadza się do znalezienie wszystkich różnic w ilości znaków w obydwu słowach, a następnie ich zsumowaniu. Należy pamiętać, że w tym zadaniu nie trzeba podawać jakie znaki zostaną usunięte, więc wystarczy skupić się na jedynie na zliczeniu różnic.

Implementacja

Wersja prosta

Zadanie można rozwiązać w czasie liniowym tworząc tablicę ilości poszczególnych znaków dla każdego słowa. Kolejnym krokiem jest zsumowanie różnic pomiędzy kolejnymi elementami obydwu tablic. W celu wygenerowania tablicy dotyczącej ilości znaków w słowie korzystamy z funkcji policzZnaki():

C++C#
Python
  1. def policzZnaki(slowo):
  2.   tab = [0 for i in range(26)]
  3.   for c in slowo:
  4.     if (c.islower()):
  5.       tab[ord(c) - ord('a')] += 1
  6.   return tab

Wtedy przykładowa implementacja wAnagramy(), która jako argumenty przyjmuje dwa słowa, wygląda następująco:

C++C#
Python
  1. def wAnagramy(slowo1, slowo2):
  2.   tab1 = policzZnaki(slowo1)
  3.   tab2 = policzZnaki(slowo2)
  4.   doUsuniecia = 0
  5.   for i in range(26):
  6.     doUsuniecia += abs(tab1[i] - tab2[i])
  7.   return doUsuniecia

Oszczędność

Kod programu można jednak uprościć poprzez deklarację tylko jednej tablicy, a nie dwóch. Należy tu skorzystać z faktu, że na koniec liczy suma różnica pomiędzy ilością każdego znaku w obu tablicach. Uproszczenie polega na tym, że jedno słowo będzie zwiększać, a drugie słowo będzie zmniejszać ilość policzonych znaków. Wtedy potrzeba jedną tablicę mniej na zapis danych jak również wykonywane jest mniej operacji arytmetycznych.

C++C#
Python
  1. def wAnagramy(slowo1, slowo2):
  2.   tab = [0 for i in range(26)]
  3.   for c in slowo1:
  4.     if (c.islower()):
  5.       tab[ord(c) - ord('a')] += 1
  6.   for c in slowo2:
  7.     if (c.islower()):
  8.       tab[ord(c) - ord('a')] -= 1
  9.   doUsuniecia = 0
  10.   for i in range(26):
  11.     doUsuniecia += abs(tab[i])
  12.   return doUsuniecia

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższego fragmentu kodu:

C++C#
Python
  1. slowo1 = input("Podaj wyrażenia:\n slowo1 = ")
  2. slowo2 = input(" slowo2 = ")
  3. wynik = wAnagramy(slowo1, slowo2)
  4. print("Usunięć:", wynik)