Kidnapper kidnaps you and writes a ransom note. He does not write it with hand, as handwriting can put him in, so reaches to a magazine at table and creates ransom note. We need to find out given ransom string and magazine string, is it possible to create given ransom note. Kidnapper can use individual characters of words.
We don't scan magazine string and ransom note separately but simultaneously. We scan character from ransom note, and check in hash table, if we find good. If not, we scan magazine string till we find the desired character.
If we reach end of magazine string, return false.
If we reach end of ransom note, return true.
int ransom_note_1(char * magazine, char *ransom){
char *mag = magazine;
char *rnote = ransom;
int hash[256];
while(*rnote != '\0'){
if(hash[(*rnote)] == 0) {
while( *mag != '\0' && *rnote != *mag){
hash[(*mag)]++;
mag++;
}
if(*mag == '\0') return false;
hash[(*rnote)]++;
mag++;
}
hash[(*rnote)]--;
rnote++;
}
return true;
}
Read full article from Algorithms and Me: Strings : Ransom Note from Magazine