211. Add and Search Word - Data structure design

[Tcdian]

211. Add and Search Word - Data structure design

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

Example

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

Note

• 你可以假设所有单词都是由小写字母 a-z 组成的。

[Tcdian]

Solution

• JavaScript Solution

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

/**
 * Adds a word into the data structure. 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = 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 data structure. A word could contain the dot character '.' to represent any one letter. 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
    return dfs(word, this.root);

    function dfs(word, root) {
        if (word === '') {
            return root.isEnd;
        }
        if (word[0] === '.') {
            return Object.keys(root.data).some((key) => dfs(word.slice(1), root.data[key]));
        }
        if (root.data[word[0]] !== undefined) {
            return dfs(word.slice(1), root.data[word[0]]);
        }
        return false;
    }
};

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

/** 
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

• TypeScript Solution

interface Dictionary {
    [key: string]: TrieNode;
}

class TrieNode {
    data: Dictionary;
    isEnd: boolean;
    constructor() {
        this.data = Object.create(null);
        this.isEnd = false;
    }
}

class WordDictionary {
    private root: TrieNode;
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word: string): void {
        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;
    }

    search(word: string): boolean {
        return dfs(word, this.root);

        function dfs(word: string, root: TrieNode): boolean {
            if (word === '') {
                return root.isEnd;
            }
            if (word[0] === '.') {
                return Object.keys(root.data).some((key) => dfs(word.slice(1), root.data[key]));
            }
            if (root.data[word[0]] !== undefined) {
                return dfs(word.slice(1), root.data[word[0]]);
            }
            return false;
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */