Problema:
Date due parole (stringhe) dire se sono anagrammi.
Input:
Due stringhe che rappresentano due parole (spazi esclusi)
Output:
Un booleano
Esempio:
Input: “nave” e “vena”
Output: true
Input: “nave” e “neve”
Output: false
Il mio ragionamento:
Se le due parole hanno un numero di caratteri differenti non possono essere anagrammi.
Calcolo il numero di occorrenze di ciascun carattere nella prima parola.
Per ogni carattere della seconda parola verifico se ce n’e’ uno corrispondente nella prima decrementando il contatore corrispondente. Se uno dei contatori e’ pari a zero prima del decremento significa che non c’e’ un numero sufficiente di caratteri e quindi ritorno false.
Nota: contare se un qualche contatore e’ rimasto maggiore di zero dopo l’ultimo foreach non e’ necessario perche’ sappiamo che le due parole hanno la stessa lunghezza. Se il numero di occorrenze di una certa lettera nella prima parola e’ maggiore rispetto al numero di occorrenze nella seconda parola, allora esistera’ sempre la situazione opposta.
La mia soluzione O(N):
static bool IsAnagram(string s1, string s2)
{
if (s1 == null) throw new ArgumentNullException("s1");
if (s2 == null) throw new ArgumentNullException("s2");
if (s1.Length != s2.Length)
return false;
uint[] counters = new uint[char.MaxValue + 1];
foreach(char c in s1)
++counters[c];
foreach(char c in s2)
if( counters[c]-- == 0) return false;
return true;
}
Mia seconda soluzione utilizzando l’idea dell’ordinamento O(N):
static class StringExtensions
{
public static char[] ToOrderedCharArray(this string s)
{
if (s == null) throw new ArgumentNullException("s");
char[] chars = new char[s.Length];
uint[] counters = new uint[char.MaxValue + 1];
foreach (char c in s) ++counters[c];
int p = 0;
for(int c = 0; c < counters.Length; ++c)
for (int i = 0; i < counters[c]; ++i)
chars[p++] = (char)c;
return chars;
}
}
static class ArrayExtensions
{
public static bool IsEquivalent<T>(this T[] array1, T[] array2)
{
if (array2 == null) throw new ArgumentNullException("vc2");
if (array1.Length != array2.Length) return false;
int n = array1.Length;
for(int i = 0; i < n; i++)
if( !array1[i].Equals(array2[i]) )
return false;
return true;
}
}
static bool IsAnagram_Sorting_Version(string s1, string s2)
{
if (s1 == null) throw new ArgumentNullException("s1");
if (s2 == null) throw new ArgumentNullException("s2");
if (s1.Length != s2.Length) return false;
char[] vc1 = s1.ToOrderedCharArray();
char[] vc2 = s2.ToOrderedCharArray();
return vc1.IsEquivalent(vc2);
}
La leggibilita’ di questa soluzione e’ indiscutibile.
La complessita’ e’ ancora O(N) anche se la performance e’ piu’ bassa rispetto alla soluzione precedente.
Inoltre questa soluzione richiede un uso maggiore della memoria per memorizzare gli array ordinati di caratteri.
Personalmente ritengo la versione precedente preferibile.