Problema:
Rimuovere tutti i caratteri duplicati da una stringa. Gli spazi devono essere preservati.
Vincoli:
Se si utilizza C++ modificare direttamente il parametro di input senza utilizzare buffer aggiuntivi.
Se si utilizza C# ritornare una nuova stringa. In quanto le stringhe sono immutabili, e’ consentito l’utilizzo del metodo ToCharArray() per attenere un buffer su cui lavorare.
Input:
Una stringa
Output:
Una stringa
Esempio:
Input: “Microsoft .Net Framework”
Output: “Microsft .Ne Famwk”
Il mio ragionamento:
Itero il buffer della stringa e costruisco all’inizio di esso la stringa risultato. Uno speciale indice mi indichera’ la posizione dell’ultimo elemento nella stringa risultato. Un nuovo carattere sara’ aggiunto solo dopo la verifica che non sia un duplicato, mentre uno spazio sara’ sempre aggiunto.
La complessita’ dell’algoritmo e’ O(N^2) dove N e’ il numero di elementi distinti presenti nella stringa.
Una soluzione piu’ efficiente consiste nell’utilizzare un vettore di booleani di appoggio per ricordarsi quali caratteri sono gia’ stati visitati. Questo evita un ciclo innestato rendendo la soluzione di complessita’ lineare.
La mia soluzione in C++:
void RemoveDuplicates(char* s)
{
if (s == NULL) throw exception("s cannot be null");
char c;
int i = 0;
int end = 0;
while(c = s[i])
{
bool duplicate = false;
if (!isspace(c))
{
for(int j = 0; j < i; ++j)
if (s[j] == c)
{
duplicate = true;
break;
}
}
if (!duplicate) s[end++] = c;
++i;
}
s[end] = 0;
}
La mia soluzione in C#:
public static class StringExtension
{
public static string RemoveDuplicates(this string s)
{
if (s == null) throw new ArgumentNullException("s");
if (s.Length < 2) return s;
char[] vc = s.ToCharArray();
int len = s.Length;
int end = 0;
for (int i = 0; i < len; ++i)
{
char c = vc[i];
bool duplicate = false;
if (!char.IsWhiteSpace(c))
for (int j = 0; j < end; j++)
if (c == vc[j])
{
duplicate = true;
break;
}
if (!duplicate)
vc[end++] = c;
}
return new string(vc, 0, end);
}
}
Soluzione in C# piu’ efficiente
public static string RemoveDuplicates(this string s)
{
if (s == null) throw new ArgumentNullException("s");
if (s.Length < 2) return s;
char[] vc = new char[s.Length];
bool[] visited = new bool[char.MaxValue + 1];
int end = 0;
foreach (char c in s)
{
if (!visited[c] || char.IsWhiteSpace(c))
{
vc[end++] = c;
visited[c] = true;
}
}
return new string(vc, 0, end);
}