Problema 1:
Fino ad ora non sapevo cosa fosse una ransom note.
Praticamente si tratta di un testo realizzato utilizzando ritagli da una rivista.
Dato il testo di una ransom note e il testo della rivista, dire se e’ possibile realizzare la ransom note.
Problema 2:
Risolvere lo stesso problema ma ritagliando parole invece che singoli caratteri.
Input:
Testo della ransom note che si vuole creare (stringa).
Testo della rivista da cui si vuole ritagliare (stringa).
Output:
True se e’ possibile realizzare la ransom note, False altrimenti.
Il mio ragionamento:
Scansiono due volte i testi e costruisco due vettori che conteggiano il numero di occorrenze di ciasun carattere. Fatto questo controllo che ci sia sempre un numero sufficiente di lettere per costruire la ransom note confrontando uno ad uno gli elementi corrispondenti di questi due array.
Per quanto riguarda il problema 2 invece di utilizzare due vettori, utilizzo due tabelle hash. La logica e’ sostanzialmente la stessa.
Le mie soluzioni:
public static bool IsCharacterRansomNotePossible(string noteText, string magazineText)
{
if (String.IsNullOrEmpty(noteText) || String.IsNullOrEmpty(magazineText))
throw new ArgumentException("noteText and/or magazineText cannot be null or empty");
const int N = Char.MaxValue + 1;
uint[] noteCount = new uint[N];
uint[] magazineCount = new uint[N];
foreach (char c in noteText) ++noteCount[c];
foreach (char c in magazineText) ++magazineCount[c];
for (int i = 0; i < N; ++i)
if (noteCount[i] > magazineCount[i])
if(!char.IsWhiteSpace((char)i))
return false;
return true;
}
public static bool IsWordRansomNotePossible(string noteText, string magazineText)
{
if (String.IsNullOrEmpty(noteText) || String.IsNullOrEmpty(magazineText))
throw new ArgumentException("noteText and/or magazineText cannot be null or empty");
var noteCount = new Dictionary<string, int>();
var magazineCount = new Dictionary<string, int>();
var noteWords = noteText.Split();
var magazineWords = magazineText.Split();
foreach (string s in noteWords)
if (noteCount.ContainsKey(s)) ++noteCount[s];
else noteCount[s] = 1;
foreach (string s in magazineWords)
if (magazineCount.ContainsKey(s)) ++magazineCount[s];
else magazineCount[s] = 1;
foreach (string word in noteCount.Keys)
if (!magazineCount.ContainsKey(word) || noteCount[word] > magazineCount[word])
return false;
return true;
}
Qualunque commento e’ ben accetto. Il codice non e’ stato testato rigorosamente.
Soluzione di Ludovico Van:
public static bool IsCharRansomNotePossible(string note, string source)
{
note = note == null ? string.Empty : note.Trim();
source = source == null ? string.Empty : source.Trim();
if (note.Length == 0)
return true;
int[] charCounts = new int[1 + char.MaxValue];
int charSetCount = 0;
foreach (char ch in note)
if (!char.IsWhiteSpace(ch))
if (charCounts[ch]++ == 0)
++charSetCount;
foreach (char ch in source)
if (charCounts[ch] != 0)
if (--charCounts[ch] == 0)
if (--charSetCount == 0)
return true;
return false;
}