ApprenticeTim

Tim the (Apprentice) Enchanter

PROBLEM STATEMENT

Apprentice Tim is learning how to use magic. However, he has a poor memory and
can't remember the exact magic words needed to cast a particular spell. In
order to figure out which magic words create which spell, he wants to just say
a long string of magic words and see what happens. But since doing so could be
hazardous (he could accidentally blow something up), he's decided that it would
be better to have a computer program tell him what happens based on what he says.

Casting a spell is as easy as saying all the magic words of the spell, in the
right order. Also, magic is a forgiving art. It is possible to cast a spell by
saying words that don't belong in the spell, as long as the correct words are
said in the correct order (the words need not be consecutive).

Given a list of all possible spells and the magic words to trigger them, and
the words that Tim chants, determine which spell was cast, if any.

DEFINITION
Class: ApprenticeTim
Method: spellCast
Parameters: String[], String
Returns: String
Method signature (be sure your method is public):  String spellCast(String[]
spellbook, String chant)

Each entry in spellbook will consist of the name of a spell, followed by one or
more magic words that must be said in order to cast that spell, all separated
by spaces. The name of the spell and the magic words themselves may not contain
spaces. The chant string will contain zero or more words, also separated by
spaces.

NOTES
- The first spell that is completed should be returned, even if there are
additional words spoken beyond the one that completed the spell.
- If multiple spells are completed with the same word, the spell that appears
first in the spellbook should be returned.
- If the method determines that no valid spell was cast, it should return an
empty string ("").
- All words are case sensitive. ("poof", "Poof", and "POOF" are all different.)

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- All Strings (both in spellbook and chant) contain only letters and spaces.
- Every pair of words in every String is separated by exactly one space, and
there are no other spaces anywhere else in the String.
- spellbook contains between 1 and 20 Strings, inclusive.
- Each String in spellbook is between 3 and 50 characters in length, inclusive.
- The chant String is between 0 and 50 characters in length, inclusive.

EXAMPLES

In each of these examples, quotes ('"'), commas (','), and curly braces ('{'
and '}') are included for clarity only.  They are never part of the input or
output.

#1:
spellbook = {"FloatingLady Abracadabra", "RabbitOutOfHat Hocus Pocus",
"DisappearingCash Alakazam"}
chant = "Hocus Pocus"

Tim cast the second spell. The method should return "RabbitOutOfHat".

#2:
spellbook = {"FloatingLady Abracadabra", "RabbitOutOfHat Hocus Pocus",
"DisappearingCash Alakazam"}
chant = "Hocus Pakus er um no its Pocus"

Even with the messed up words in between, Tim still said "Hocus" and "Pocus",
in that order. The method should return "RabbitOutOfHat".

#3:
spellbook = {"PUFF Tal Ken Ni Zap", "POOF Tal Ken Ni", "BOOM Tal Ken"}
chant = "Tal Ken Ni Zap"

The third spell is the first to finish; the remaining two words in the chant
are ignored. The method should return "BOOM".

#4:
spellbook = {"WhiteSmoke Nini Weep", "RedSmoke Weep Bom", "YellowSmoke Bah
Bom", "GreenSmoke Yaya Bom", "BlueSmoke Nini Bom", "PurpleSmoke Grahna Bom"}
chant = "Bah Weep Grahna Weep Nini Bom"

The word "Bom" completed four spells all at once. The method should return the
one that appears first in the spellbook, "RedSmoke". Note that the first spell
"WhiteSmoke" is not completed; even though both "Nini" and "Weep" appear in
chant, they are in the wrong order.

#5:
spellbook = {"Fun YAY"}
chant = "yay"

"YAY" and "yay" are not the same. The method should return "".

#6:
spellbook = {"Fun YAY"}
chant = ""

No chant, no spell. The method should return "".