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():

  1. int * policzZnaki(string slowo) {
  2.   int * tab = new int[26];
  3.   for (int i = 0; i < 26; i++) {
  4.     tab[i] = 0;
  5.   }
  6.   for (int i = 0; i < slowo.length(); i++) {
  7.     if (islower(slowo[i])) {
  8.       tab[slowo[i] - 'a']++;
  9.     }
  10.   }
  11.   return tab;
  12. }

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

  1. int wAnagramy(string slowo1, string slowo2) {
  2.   int * tab1 = policzZnaki(slowo1);
  3.   int * tab2 = policzZnaki(slowo2);
  4.   int doUsuniecia = 0;
  5.   for (int i = 0; i < 26; i++) {
  6.     doUsuniecia += abs(tab1[i] - tab2[i]);
  7.   }
  8.   return doUsuniecia;
  9. }

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.

  1. int wAnagramy(string slowo1, string slowo2) {
  2.   int * tab = new int[26];
  3.   for (int i = 0; i < 26; i++) {
  4.     tab[i] = 0;
  5.   }
  6.   for (int i = 0; i < slowo1.length(); i++) {
  7.     if (islower(slowo1[i])) {
  8.       tab[slowo1[i] - 'a']++;
  9.     }
  10.   }
  11.   for (int i = 0; i < slowo2.length(); i++) {
  12.     if (islower(slowo2[i])) {
  13.       tab[slowo2[i] - 'a']--;
  14.     }
  15.   }
  16.   int doUsuniecia = 0;
  17.   for (int i = 0; i < 26; i++) {
  18.     doUsuniecia += abs(tab[i]);
  19.   }
  20.   return doUsuniecia;
  21. }

Testowanie funkcji

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

  1. int main () {
  2.   string slowo1, slowo2;
  3.   cout << "Podaj wyrazenia:\n slowo1 = ";
  4.   getline(cin, slowo1);
  5.   cout << " slowo2 = ";
  6.   getline(cin, slowo2);
  7.   int wynik = wAnagramy(slowo1, slowo2);
  8.   cout << "Usuniec: " << wynik;
  9.   system("pause");
  10.   return 0;
  11. }