中級 0件解決済み 正答率0%

スペルチェッカー

大文字小文字と句読点を無視して、辞書にない単語をテキストから列挙します。

このチャレンジで学べること

  • 単語をセットに読み込んで高速に検索する
  • 文字のルールに従ってテキストを単語に分割する
  • 重複なしで、最初に現れた順に結果を報告する

問題

原文(英語)を表示

ワープロソフトは、知らない単語に下線を引きます。検索を速くするために辞書をセット(ハッシュテーブル)に読み込み、それからテキストを走査しましょう。

単語とは、英字(A-Z、a-z)とアポストロフィが続く、できるだけ長い並びのことです。それ以外の文字(スペース、数字、句読点)は単語の区切りになります。単語は大文字と小文字を区別せずに比較するので、The は辞書の the に一致します。

spell_checker(dictionary, text) を実装してください。

入力

dictionary: 既知の単語。大文字と小文字は混在していても構いません。

text: チェックするテキスト。

出力

つづりの誤った単語を小文字にして、テキストに最初に現れた順に、それぞれ1回だけ返してください。すべての単語が既知なら空のリストを返します。

制約

0 ≤ 辞書の単語数 ≤ 2,000

0 ≤ text の長さ ≤ 10,000

例

例 1
入力:
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"] です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。