問題
ワープロソフトは、知らない単語に下線を引きます。検索を速くするために辞書をセット(ハッシュテーブル)に読み込み、それからテキストを走査しましょう。
単語とは、英字(A-Z、a-z)とアポストロフィが続く、できるだけ長い並びのことです。それ以外の文字(スペース、数字、句読点)は単語の区切りになります。単語は大文字と小文字を区別せずに比較するので、The は辞書の the に一致します。
spell_checker(dictionary, text) を実装してください。
入力
dictionary: 既知の単語。大文字と小文字は混在していても構いません。
text: チェックするテキスト。
出力
つづりの誤った単語を小文字にして、テキストに最初に現れた順に、それぞれ1回だけ返してください。すべての単語が既知なら空のリストを返します。
制約
0 ≤ 辞書の単語数 ≤ 2,000
0 ≤ text の長さ ≤ 10,000
例
入力:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
期待される出力:
expected = ["teh", "cta"]
入力:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
期待される出力:
std::vector<std::string> expected = {"teh", "cta"};
入力:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
期待される出力:
string[] expected = new string[] {"teh", "cta"};
解説
teh と cta は辞書にありません。ほかの単語は大文字小文字やカンマに関係なく一致します。結果は ["teh", "cta"] です。
入力:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
期待される出力:
expected = ["dont"]
入力:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
期待される出力:
std::vector<std::string> expected = {"dont"};
入力:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
期待される出力:
string[] expected = new string[] {"dont"};
解説
don't はアポストロフィを含んだまま一致します。dont は未知の単語なので、1回だけ挙げます。結果は ["dont"] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
セットを作るときに、辞書の単語を一度だけ小文字にしておきましょう。
ヒント 2
現在の単語を1文字ずつ組み立て、英字でもアポストロフィでもない文字に出会ったら単語を区切ります。
ヒント 3
すでに報告した単語を記録するセットをもう1つ用意しましょう。
目安の計算量
時間 O(D + T)、追加メモリ O(D + T)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。