StartsWith
Lektion 7 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Der einzige Grund, warum Tries existieren, ist die schnelle Beantwortung von Präfix-Fragen. startsWith prüft, ob irgendein gespeichertes Wort mit einem bestimmten Präfix beginnt – es spielt keine Rolle, ob dieses Präfix selbst ein vollständiges eingefügtes Wort ist.
Der Durchlauf ist fast identisch mit search: Folgen Sie von der Wurzel aus den Kindknoten Zeichen für Zeichen. Wenn ein Zeichen auf dem Weg fehlt, beginnt kein gespeichertes Wort mit diesem Präfix, geben Sie also false zurück. Wenn Sie jedes Zeichen ohne Unterbrechung durchlaufen, ist die Antwort true – der Teilbaum unter diesem Knoten enthält mindestens ein gespeichertes Wort.
Der einzige Unterschied zu search: Es gibt am Ende keine isEndOfWord-Prüfung. Das Erreichen des Endes des Präfixes ist ausreichend.
Aufgabe
EinfachFügen Sie der Klasse Trie eine Methode startsWith hinzu.
Sie erhält einen String prefix und gibt Folgendes zurück:
true, wenn ein bereits eingefügtes Wort mitprefixbeginnt (das Präfix kann mit einem vollständigen Wort übereinstimmen oder der vordere Teil eines längeren Wortes sein).falseandernfalls.
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
}
return 0;
}