Welche Datenstruktur wird zum Speichern eines Absatzes verwendet?

Question

Kürzlich fragte mich ein Interviewer 1. Welche Datenstruktur sollte verwendet werden, wenn Sie einen Absatz speichern, später durchqueren und ein Wort finden müssen? 2. Welche Datenstruktur wird verwendet, wenn Sie in diesem Absatz auch Wörter hinzufügen, bearbeiten oder löschen können?

Kann mir jemand bei der Antwort helfen? Und wenn möglich, kann auch jemand ähnliche Fragen mit logischen Antworten zu Datenstrukturen posten, wie ich mich auf Interviews vorbereite.

Answer 1

Ich denke, was Sie suchen, ist ein Trie. A trie ein Baum, dessen Knoten eindeutige Kombinationen von Buchstaben (Präfixe) speichern, und deren Kanten auf Kombinationen von Buchstaben zeigen, die diesen Präfixen (Suffixen) folgen. Versuche können aus Textdokumenten erstellt werden, um O (L) Such-, Einfüge- und Löschzeiten zu geben (L ist die Länge des Wortes, nach dem Sie suchen, hinzufügen oder löschen). Versuche werden häufig in Autocomplete- und Dokumentensuchalgorithmen verwendet.