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;
}