Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Rechtschreibprüfung

Liste die Wörter eines Texts auf, die nicht im Wörterbuch stehen, ohne auf Groß- und Kleinschreibung und Satzzeichen zu achten.

Das lernst du

  • Wörter für schnelles Nachschlagen in ein Set laden
  • Text nach einer Zeichenregel in Wörter zerlegen
  • Ergebnisse in der Reihenfolge des ersten Auftretens ohne Duplikate ausgeben

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

Beispiel 1
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"].

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.