Problem
Ein Textverarbeitungsprogramm unterstreicht Wörter, die es nicht kennt. Lade das Wörterbuch in eine Menge (ein Set auf Basis einer Hashtabelle), damit jedes Nachschlagen schnell geht, und durchsuche dann den Text.
Ein Wort ist eine möglichst lange Folge aus englischen Buchstaben (A-Z, a-z) und Apostrophen; jedes andere Zeichen (Leerzeichen, Ziffern, Satzzeichen) trennt Wörter. Beim Vergleich spielt Groß- und Kleinschreibung keine Rolle, also passt The zum Wörterbucheintrag the.
Implementiere spell_checker(dictionary, text).
Eingabe
dictionary: Die bekannten Wörter, in beliebiger Groß- und Kleinschreibung.
text: Der zu prüfende Text.
Ausgabe
Gib die falsch geschriebenen Wörter in Kleinbuchstaben zurück, in der Reihenfolge ihres ersten Auftretens im Text und jedes nur einmal. Sind alle Wörter bekannt, gib eine leere Liste zurück.
Einschränkungen
0 ≤ Größe des Wörterbuchs ≤ 2000
0 ≤ Länge von text ≤ 10 000
Beispiele
Eingabe:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
Erwartete Ausgabe:
expected = ["teh", "cta"]
Eingabe:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
Erwartete Ausgabe:
std::vector<std::string> expected = {"teh", "cta"};
Eingabe:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
Erwartete Ausgabe:
string[] expected = new string[] {"teh", "cta"};
Erläuterung
teh und cta stehen nicht im Wörterbuch. Bei den übrigen Wörtern spielen Groß- und Kleinschreibung und das Komma keine Rolle: ["teh", "cta"].
Eingabe:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
Erwartete Ausgabe:
expected = ["dont"]
Eingabe:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
Erwartete Ausgabe:
std::vector<std::string> expected = {"dont"};
Eingabe:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
Erwartete Ausgabe:
string[] expected = new string[] {"dont"};
Erläuterung
don't behält seinen Apostroph und wird gefunden; dont ist unbekannt und wird einmal aufgeführt: ["dont"].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Wandle die Wörterbuchwörter einmal beim Aufbau des Sets in Kleinbuchstaben um.
Hinweis 2
Bau das aktuelle Wort Zeichen für Zeichen auf und schließe es ab, sobald du auf ein Zeichen triffst, das weder Buchstabe noch Apostroph ist.
Hinweis 3
Führe ein zweites Set mit den Wörtern, die du schon gemeldet hast.
Erwartete Komplexität
Zeit O(D + T), zusätzlicher Speicher O(D + T)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.