動機

就是trie

Problem

A trie (pronounced as try) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() Initializes the trie object.
  • void insert(String word) Inserts the string word into the trie.
  • boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

 

Example 1:

Input[Trie, insert, search, search, startsWith, insert, search][[], [apple], [apple], [app], [app], [app], [app]]Output[null, null, true, false, true, null, true]ExplanationTrie trie = new Trie();trie.insert(apple);trie.search(apple);   // return Truetrie.search(app);     // return Falsetrie.startsWith(app); // return Truetrie.insert(app);trie.search(app);     // return True

 

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Sol

每一個node有[flag :: bool, hash{char -> Node}]

flag是指到此是不是某個單字的終點

class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.t = [False, {}]

    def insert(self, w: str) -> None:
        """
        Inserts a word into the trie.
        """
        tmp = self.t
        for c in w:
            if c not in tmp[1]:
                tmp[1][c] = [False, {}]
            tmp = tmp[1][c]
        tmp[0] = True

    def search(self, w: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tmp = self.t
        for c in w:
            if c not in tmp[1]:
                return False
            tmp = tmp[1][c]
        return tmp[0]

    def startsWith(self, p: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tmp = self.t
        for c in p:
            if c not in tmp[1]:
                return False
            tmp = tmp[1][c]
        return True

另外有C++版

struct Trie {
   unordered_map<char, struct Trie*> nextLevel;
   bool end;
    
    ~Trie() {
        for (auto& kv : nextLevel) {
            delete kv.second;
        }
    }

   void insert(string s) {
        Trie* trie = this;
        for (auto& c : s) {
            if (trie->nextLevel.find(c) == trie->nextLevel.end()) {
                trie->nextLevel[c] = new Trie();
            }
            trie = trie->nextLevel[c];
        }
        trie->end = 1;
    }

    bool search(string s) {
        Trie* trie = this;
        for (auto& c : s) {
            if (trie->nextLevel.find(c) != trie->nextLevel.end()) {
                trie = trie->nextLevel[c];
            } else {
                return 0;
            }
        }
        return trie->end;
    }
    
    bool startsWith(string s) {
        Trie* trie = this;
        for (auto& c : s) {
            if (trie->nextLevel.find(c) != trie->nextLevel.end()) {
                trie = trie->nextLevel[c];
            } else {
                return 0;
            }
        }
        return 1;
    }
};