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 – Determinare se in una stringa tutti i caratteri sono diversi tra loro


Problema 1:

Determinare se in una stringa tutti i caratteri sono diversi tra loro.

Problema 2:

Risolvere il problema 1 senza usare strutture dati aggiuntive.

Input:

Una stringa

Output:

Un booleano

Il mio ragionamento:

Sfrutto un vettore di booleani con un numero di elementi pari a tutti i possibili caratteri. Itero la stringa e per ogni carattere setto il corrispondente elemento del vettore a true. Se prima di settare lo trovo gia’ a true significa che quello e’ un carattere ripetuto e restituisco subito false. Se si termina l’iterazione allora ritorno true.

Senza strutture dati non si puo’ fare altro che controllare ogni coppia di caratteri.

Le mie soluzioni:

public static bool IsStringWithUniqueCharacters1(string s)
{
    if (s == null) throw new ArgumentNullException("s");
    if (s.Length < 2) return true;

    bool[] flags = new bool[Char.MaxValue + 1];

    foreach (char c in s)
        if (flags[(int)c]) return false;
        else flags[(int)c] = true;

    return true;
}

public static bool IsStringWithUniqueCharacters2(string s)
{
    if (s == null) throw new ArgumentNullException("s");
    if (s.Length < 2) return true;

    int n = s.Length;

    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (s[i] == s[j]) return false;

    return true;
}

Print | posted on Thursday, September 2, 2010 11:44 PM |

Feedback

Gravatar

# re: Algoritmi – Determinare se in una stringa tutti i caratteri sono diversi tra loro

Entrambi i problemi possono essere risolti agilmente ordinando le lettere all'interno della stringa, quindi verificando ogni lettera con la successiva

es.:
aiuolE -> aeilou -> ae;ei;il;lo;ou -> true
aiuolA -> aailou -> aa -> false
9/3/2010 7:18 AM | Marco
Gravatar

# re: Algoritmi – Determinare se in una stringa tutti i caratteri sono diversi tra loro

oppure con linq, estraendo il charArray della stringa, il distinct e la verifica che la lunghezza dell'array "distinct" sia uguale o meno a quella della stringa originale
9/3/2010 1:37 PM | Roberto
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET