考虑用Tire

• 一个个一个遍历
• 需要节约空间
• 查找前缀

208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

S: 树结构，标记尾节点 O(1)

因为只有26个字母可以直接用数组代替hashmap

class TrieNode {
public:
    // Initialize your data structure here.
    char letter;
    bool leaf;
    unordered_map<char, TrieNode*> children;
    TrieNode(char x): letter(x), leaf(false) {}
};

class Trie {
public:
    Trie() {
        root = new TrieNode('#');
    }

    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->children.find(word[i]) == cur->children.end()) {
                TrieNode* node = new TrieNode(word[i]);
                cur->children[word[i]] = node;
                cur = node;
            } else {
                cur = cur->children[word[i]];
            }
        }
        cur->leaf = true;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        if (word.size() == 0) {
            return false;
        }
        TrieNode* cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->children.find(word[i]) == cur->children.end()) {
                return false;
            }
            cur = cur->children[word[i]];
        }
        if (cur->leaf) {
            return true;
        } else {
            return false;
        }
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        if (prefix.size() == 0) {
            return false;
        }
        TrieNode* cur = root;
        for (int i = 0; i < prefix.size(); ++i) {
            if (cur->children.find(prefix[i]) == cur->children.end()) {
                return false;
            }
            cur = cur->children[prefix[i]];
        }
        return true;
    }

private:
    TrieNode* root;
};

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only lettersa-zor.. A.means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

S: Trie

struct Trie{
    char letter;
    bool leaf;
    vector<Trie*> children;
    Trie(char c, bool l): letter(l), leaf(l), children(vector<Trie*>(26, NULL)) {}
};
class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Trie('#', false);
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        Trie* node = root;
        int n = word.size();
        if (n == 0) return;
        for (int i = 0; i < n; ++i) {
            if (node->children[word[i] - 'a'] == NULL) {
                node->children[word[i] - 'a'] = new Trie(word[i], false);
            } 
            node = node->children[word[i] - 'a'];
        }
        node->leaf = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return bfs(root, word, 0);
    }

    bool bfs(Trie* node, string word, int pos) {
        if (pos == word.size()) {
            return node->leaf;
        }
        if (word[pos] == '.') {
            for (int i = 0; i < 26; ++i) {
                if (node->children[i] && bfs(node->children[i], word, pos + 1)) {
                    return true;
                }
            }
        } else if (node->children[word[pos] - 'a'] != NULL) {
            return bfs(node->children[word[pos] - 'a'], word, pos + 1);
        } 
        return false;
    }

private:
    Trie *root;
};

Trie Service

Build tries from a list of pairs. Save top 10 for each node.

Example

Given a list of

<
"abc", 2
>
<
"ac", 4
>
<
"ab", 9
>

Return <a[9,4,2]<b[9,2]<c[2]<>>c[4]<>>>, and denote the following tree structure:

         Root
         / 
       a(9,4,2)
      /    \
    b(9,2) c(4)
   /
 c(2)

/**
 * Definition of TrieNode:
 * class TrieNode {
 * public:
 *     TrieNode() {}
 *     map<char, TrieNode*> children;
 *     vector<int> top10;
 * };
 */
class TrieService {
private:
    TrieNode* root;

public:
    TrieService() {
        root = new TrieNode();
    }

    TrieNode* getRoot() {
        // Return root of trie root, and 
        // lintcode will print the tree struct.
        return root;
    }

    void insert(string& word, int frequency) {
        if (word.size() < 1) {
            return;
        }
        TrieNode* cur = root;
        for (int i = 0; i < word.size(); ++i) {
            if (cur->children.find(word[i]) == cur->children.end()) {
                TrieNode* node = new TrieNode;
                node->top10.push_back(frequency);
                cur->children[word[i]] = node;
                cur = node;
            } else {
                updateTop10(cur->children[word[i]]->top10, frequency);
                cur = cur->children[word[i]];
            }
        }
    }

    void updateTop10(vector<int>& nums, int freq) {
        nums.push_back(freq);
        sort(nums.begin(), nums.end(), greater<int>());
    }
};