簡介：中等，題意為實作Trie (prefix tree 前綴樹)，可以使用Linked list, map, set去實作。

一、Linked list

（一）結構

用Linked list建構的trie，其紀錄abc和abde兩字。

上圖為用linked list建構的trie，每一個節點有兩個資料，分別為：

isRecorded：這個字是否被紀錄，如：abc和abde有被記錄，但ab沒被記錄。
children：一個指向節點的26格陣列，每一格代表一個英文字母，如果指向NULL，則代表此字母沒有被紀錄；如果有指向節點，則代表此字母有被紀錄。

以下為程式碼：

class TrieNode {
public:
    bool isRecorded;
    std::vector<TrieNode*> children;
    
    TrieNode()
    :isRecorded(false),
     children(std::vector (26, NULL)){}
};
class Trie {
public:
    TrieNode* root;
    
    Trie():root(new TrieNode()){}
    void insert(std::string word);
    bool search(std::string word);
    bool startsWith(std::string prefix);
};

（二）插入字詞

void Trie::insert(std::string word) {
    TrieNode* node = root;
    for (auto w : word) {
        const int index = w - 'a';
        // If the node have not a corresponding child, add a new child to it.
        if (node->children[index] == NULL) {node->children[index] = new TrieNode();}
        // Move to the next node
        node = node->children[index];
    }
    node->isRecorded = true;
}

以上是insert()程式碼，時間複雜度為字詞 (word)長度。

Line 3 for loop：只要把字詞的每一個字母依照順序和trie做比較即可。
Line 6：如果此字母指向NULL，就讓他指向一個新節點。
Line 8：移至下一個節點。
Line 10：比較結束後，更新isRecorded為true。

（三）搜尋字詞

bool Trie::search(std::string word) {
    TrieNode* node = root;
    for (auto w : word) {
        const int index = w - 'a';
        // If the node have not a corresponding child, the trie does not store the word.
        if (node->children[index] == NULL) {return false;}
        // Move to the next node
        node = node->children[index];
    }
    return node->isRecorded;
}

以上是search()程式碼，時間複雜度為字詞 (word)長度。搜尋的邏輯和插入很像，都要每個字母和trie做比較，比較不同的部分為：

Line 6：如果此字母指向NULL，就直接回傳false，因為此字母沒有被記錄。
Line 10：比較結束後，直接回傳isRecorded。

（四）搜尋前綴

bool Trie::startsWith(std::string prefix) {
    TrieNode* node = root;
    for (auto p : prefix) {
        const int index = p - 'a';
        // If the node have not a corresponding child, the trie does not store the prefiex.
        if (node->children[index] == NULL) {return false;}
        // Move to the next node
        node = node->children[index];
    }
    return true;
}

以上是startWith()程式碼，時間複雜度為字詞 (word)長度。搜尋前綴和字詞的邏輯一樣，只不過在Line10中，直接回傳true。

二、Map and set

（一）Map

用map建構的trie，其紀錄abc和abde兩字。

上圖為用linked list建構的trie，這裡使用兩個Map分別去紀錄前綴 (prefix)與字詞 (word)，以下為程式碼。

class TrieMap {
public:
    std::map<std::string, bool> prefixMap;
    std::map<std::string, bool> wordMap;
    
    TrieMap(){}
    void insert(std::string word);
    bool search(std::string word);
    bool startsWith(std::string prefix);
};

void TrieMap::insert(std::string word) {
    // Store word
    wordMap[word] = true;
    // Store prefix
    string key = "";
    for (int i = 0; i < word.size(); ++i) {
        key += word[i];
        prefixMap[key] = true;
    }
}

bool TrieMap::search(std::string word) {
    return wordMap[word];
}

bool TrieMap::startsWith(std::string prefix) {
    return prefixMap[prefix];
}

插入有兩部分：

Word：直接加入字詞，時間複雜度為 log(字詞總數)。
Prefix：每個前綴依序加入，時間複雜度為字綴長度*log(前綴總數)。

搜尋字詞與前綴就直接回傳map即可，如果不在map裡的字，operator[]會將此字加入map中，並給予false。

（二）Set

在Map中，我們使用兩個map去紀錄word和prefix，但事實上我們只需要wordMap即可。然後你應該會發現，map紀錄的true很冗餘吧？所以我們也不用map，只要set就好。實作如下：

class TrieSet {
public:
    std::set<std::string> strSet;
    
    TrieSet(){}
    void insert(std::string word);
    bool search(std::string word);
    bool startsWith(std::string prefix);
};

void TrieSet::insert(std::string word) {
    strSet.insert(word);
}

bool TrieSet::search(std::string word) {
    return  strSet.find(word) != strSet.end();
}

bool TrieSet::startsWith(std::string prefix) {
    auto it = strSet.lower_bound(prefix);
    if (it == strSet.end()) {return false;}
    for (size_t i = 0; i < prefix.size(); ++i) {
        if (prefix[i] != (*it)[i]) {return false;}
    }
    return true;
}

插入就直接把字詞放入集合中，而搜尋字詞就在集合中搜尋此字即可。最後搜尋前綴就要利用lower_bound()去找出和字詞最像的元素出來，然後比較這兩前綴是否一致？

三、相關文章

請詳見LeetCode相關文章

宗平方 TsungSquare

搜尋此網誌

［刷題］208 Implement Trie (Prefix Tree) ｜C++｜LeetCode