208. Implement Trie (Prefix Tree)

[Tcdian]

208. Implement Trie (Prefix Tree)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

Example

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note

• 你可以假设所有的输入都是由小写字母 a-z 构成的。
• 保证所有输入均为非空字符串。

[Tcdian]

Solution

• JavaScript Solution

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.root = new TrieNode();
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let patrol = this.root;
    for (let i = 0; i < word.length; i++) {
        patrol.data[word[i]] = patrol.data[word[i]] || new TrieNode();
        patrol = patrol.data[word[i]];
    }
    patrol.isEnd = true;
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let patrol = this.root;
    for (let i = 0; i < word.length; i++) {
        if ((patrol = patrol.data[word[i]]) === undefined) {
            return false;
        }
    }
    return patrol.isEnd;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let patrol = this.root;
    for (let i = 0; i < prefix.length; i++) {
        if ((patrol = patrol.data[prefix[i]]) === undefined) {
            return false;
        }
    }
    return true;
};

function TrieNode() {
    this.data = Object.create(null);
    this.isEnd = false;
}

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */