1032. Stream of Characters

[Tcdian]

1032. Stream of Characters

按下述要求实现 StreamChecker 类：

• StreamChecker(words)：构造函数，用给定的字词初始化数据结构。
• query(letter)：如果存在某些 k >= 1，可以用查询的最后 k 个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。

Example

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

Note

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 2000
• 字词只包含小写英文字母。
• 待查项只包含小写英文字母。
• 待查项最多 40000 个。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string[]} words
 */
var StreamChecker = function(words) {
    this.root = new TrieNode;
    this.queried = '';
    const insert = (word) => {
        let patrol = this.root;
        for (let i = word.length - 1; i >= 0; i--) {
            patrol.data[word[i]] = patrol.data[word[i]] || new TrieNode();
            patrol = patrol.data[word[i]];
        }
        patrol.isEnd = true;
    };
    words.forEach((word) => {
        insert(word);
    });
};

/** 
 * @param {character} letter
 * @return {boolean}
 */
StreamChecker.prototype.query = function(letter) {
    let patrol = this.root;
    this.queried = letter + this.queried;
    for (let i = 0; i < this.queried.length; i++) {
        patrol = patrol.data[this.queried[i]];
        if (patrol === undefined) {
            return false;
        }
        if (patrol.isEnd) {
            return true;
        }
    }
    return false;
};

/** 
 * Your StreamChecker object will be instantiated and called as such:
 * var obj = new StreamChecker(words)
 * var param_1 = obj.query(letter)
 */

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

• TypeScript Solution

interface TrieNodeData {
    [properName: string]: TrieNode;
}

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

class StreamChecker {
    private root: TrieNode;
    private queried: string;
    constructor(words: string[]) {
        this.root = new TrieNode;
        this.queried = '';
        words.forEach((word) => {
            this.insert(word);
        });
    }

    private insert(word: string) {
        let patrol = this.root;
        for (let i = word.length - 1; i >= 0; i--) {
            patrol.data[word[i]] = patrol.data[word[i]] || new TrieNode();
            patrol = patrol.data[word[i]];
        }
        patrol.isEnd = true;
    }

    query(letter: string): boolean {
        let patrol = this.root;
        this.queried = letter + this.queried;
        for (let i = 0; i < this.queried.length; i++) {
            patrol = patrol.data[this.queried[i]];
            if (patrol === undefined) {
                return false;
            }
            if (patrol.isEnd) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * var obj = new StreamChecker(words)
 * var param_1 = obj.query(letter)
 */