GCJ2011 Round1A 問題B(smallだけ)

問題

あなたはSeanとハングマンというゲームをやる。これは、順にアルファベットを言っていき、選んだ単語にそのアルファベットがあればそこだけ公開、なければ-1点。あなたは辞書Dの中から1単語選ぶ。Seanはアルファベットリストがあって、そのリストの順に言っていく。ただし、その単語があり得なければ言わない。これを繰り返していく。
辞書の単語の中で一番Seanの点数を低くできる単語を返せ。複数あるならば辞書に最初にでてくる単語を返せ。

考え方

smallはとりあえず愚直にシミュレーションした。
気を付けるところは、「a」と言ってmysteryワードが「_a__」となった場合、2番目がaじゃない単語を省くだけじゃなくて、「_a_a」のようにmysteryワードの中で「_」の部分に「a」が含まれるようなワードも候補から消えること。
これじゃ、O(辞書の単語数*候補数*リストの数)なので、O(N^2 M)。