Wort-Segmentierung
Lektion 14 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Gegeben ein String s und ein Wörterbuch von Wörtern, können wir s in eine Sequenz von Wörterbuchwörtern zerlegen, ohne dass etwas übrig bleibt? "leetcode" lässt sich als "leet" + "code" zerlegen, wenn beide im Wörterbuch enthalten sind; "catsandog" lässt sich nicht zerlegen, egal wie wir es schneiden.
Ein Durchlauf mit dynamischer Programmierung löst das Problem. Definiere dp[i] als können die ersten i Zeichen segmentiert werden? Beginne mit dp[0] = true. Für jedes i, bei dem dp[i] true ist, durchlaufe den Trie ab Position i im String; jedes Mal, wenn der Durchlauf auf einem isEndOfWord-Knoten bei Index j landet, setze dp[j+1] = true.
Der Trie macht jeden Durchlauf schnell: Ein einzelnes fehlendes Zeichen beendet ihn. Die endgültige Antwort befindet sich in dp[n].
Aufgabe
MittelSchreiben Sie eine Funktion wordBreak, die einen String s und ein String-Array dictionary erhält und true zurückgibt, wenn s in ein oder mehrere leerzeichenfreie Stücke zerlegt werden kann, die alle im Dictionary enthalten sind, andernfalls false.
Ein leerer String s ist immer zerlegbar.
Sie müssen die Trie-Klasse verwenden (bereitgestellt in trie zusammen mit trienode) – verwenden Sie keine in der Sprache eingebauten Funktionen wie Sets, Dicts oder Maps zum Zählen/Verfolgen.
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}
Alle Lektionen in Tries - Datenstrukturen-Serie #8
3Übungsaufgaben
Längster gemeinsamer PräfixWörter mit Präfix zählenAutovervollständigungLängstes Wort im WörterbuchWort-Segmentierung