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. static int[] policzZnaki(string slowo) {
  2.   int[] tab = new int[26];
  3.   for (int i = 0; i < slowo.Length; i++) {
  4.     if (char.IsLower(slowo[i])) {
  5.       tab[slowo[i] - 'a']++;
  6.     }
  7.   }
  8.   return tab;
  9. }

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

  1. static 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 += Math.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. static int wAnagramy(string slowo1, string slowo2) {
  2.   int[] tab = new int[26];
  3.   for (int i = 0; i < slowo1.Length; i++) {
  4.     if (char.IsLower(slowo1[i])) {
  5.       tab[slowo1[i] - 'a']++;
  6.     }
  7.   }
  8.   for (int i = 0; i < slowo2.Length; i++) {
  9.     if (char.IsLower(slowo2[i])) {
  10.       tab[slowo2[i] - 'a']--;
  11.     }
  12.   }
  13.   int doUsuniecia = 0;
  14.   for (int i = 0; i < 26; i++) {
  15.     doUsuniecia += Math.Abs(tab[i]);
  16.   }
  17.   return doUsuniecia;
  18. }

Testowanie funkcji

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

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj wyrażenia:\n slowo1 = ");
  3.   string slowo1 = Console.ReadLine();
  4.   Console.Write(" slowo2 = ");
  5.   string slowo2 = Console.ReadLine();
  6.   int wynik = wAnagramy(slowo1, slowo2);
  7.   Console.WriteLine("Usunięć: {0}", wynik);
  8.   Console.ReadKey();
  9. }