leetcode演算法之前綴樹(字典樹)

今天來盤一盤 **前綴樹(字典樹) ** 這類題目

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

前綴樹(字典樹)

前綴樹是用來存儲字元串的。前綴樹的每一個節點代表一個字元串（前綴）。每一個節點會有多個子節點，通往不同子節點的路徑上有著不同的字元。子節點代表的字元串是由節點本身的原始字元串 ，以及通往該子節點路徑上所有的字元組成的。

前綴樹的一個重要的特性是，節點所有的後代都與該節點相關的字元串有著共同的前綴。

  • 208 實現 Trie (前綴樹)（medium）
  • 211 添加與搜索單詞 - 數據結構設計(medium)

208 實現 Trie (前綴樹)

class Trie {

private:
    bool isEnd;
    Trie* nextNode[26];

public:
    /** Initialize your data structure here. */
    Trie() {
        isEnd = false;
        memset(nextNode, 0, sizeof(nextNode));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* node = this;
        for (char c : word){
            if (node->nextNode[c - 'a'] == nullptr)
                node->nextNode[c - 'a'] = new Trie();
            node = node->nextNode[c - 'a'];
        }
        node->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* node = this;
        for (char c: word){
            node = node->nextNode[c - 'a'];
            if (node == nullptr) return false;
        }
        return node->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c: prefix){
            node = node->nextNode[c - 'a'];
            if (node == nullptr) return false;
        }
        return true;        
    }
};

211 添加與搜索單詞 - 數據結構設計

class WordDictionary {

private:
    bool isEnd;
    WordDictionary* nextNode[26];
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        isEnd = false;
        memset(nextNode, 0, sizeof(nextNode));
    }
    
    void addWord(string word) {
        WordDictionary* node = this;
        for (char c : word){
            int index = c - 'a';
            if (node->nextNode[index] == nullptr)
                node->nextNode[index] = new WordDictionary();
            node = node->nextNode[index];
        }
        node->isEnd = true;

    }
    
    bool search(string word) {
        auto node = this;
        return match(word, node, 0);
    }
    bool match(string word, WordDictionary* node, int start){
        if (node == nullptr) return false;
        if (start == word.size()) return node->isEnd;

        auto ch = word[start];
        if (ch != '.'){
            int index = ch - 'a';
            if (node->nextNode[index] == nullptr)
                return false;
            node = node->nextNode[index];
            return match(word, node, start + 1);
        }
        else{
            for (auto ch = 'a'; ch <= 'z'; ch++){
                int index = ch - 'a';
                if (match(word, node->nextNode[index], start + 1))
                    return true;
            }
        }
        return false;
    }
};

更多分類刷題資料

Tags:

VirMach 便宜 VPS