Angella Andrea - Italian Blog

Infinita passione per lo sviluppo software !
posts - 133, comments - 216, trackbacks - 9

My Links

News

MIT OpenCourseWare: I'm invested Wikipedia Affiliate Button


Sto leggendo:

Archives

Post Categories

Siti web realizzati

Siti web tecnici

Algoritmi – Dire se due parole sono anagrammi


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.

Print | posted on Saturday, September 4, 2010 4:48 PM | Filed Under [ Algoritmica ]

Feedback

Gravatar

# re: Algoritmi – Dire se due parole sono anagrammi

Nel codice presentato il true indica solo che la prima parola è contenuta nella seconda, manca la verifica che l'array counter abbia somma interna uguale a 0.
9/4/2010 10:36 PM | Marco
Gravatar

# re: Algoritmi – Dire se due parole sono anagrammi

Ciao Andrea,

se assumiamo di poter allocare memoria extra come nella tua soluzione con un array di contatori, allora anche l'algoritmo di ordinamento può diventare O(N) :-)

Secondo me, la soluzione di Roberto basata sul sort è molto buona perché è semplice e si capisce subito come funziona...
9/6/2010 2:47 PM | xpmatteo
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET