LeetCode [1032] Stream of Characters

 1032. Stream of Characters

Hard

Implement the StreamChecker class as follows:

• StreamChecker(words): Constructor, init the data structure with the given words.
• query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

 

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
• Words will only consist of lowercase English letters.
• Queries will only consist of lowercase English letters.
• The number of queries is at most 40000.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

class StreamChecker { class TrieNode{ char ch; boolean isLeaf; TrieNode[] children; TrieNode(){ isLeaf = false; children = new TrieNode[26]; } TrieNode(char c){ ch = c; isLeaf = false; children = new TrieNode[26]; } } TrieNode root; Queue<TrieNode> que = new LinkedList<>(); void build(String word){ TrieNode p = root; for(char c : word.toCharArray()){ if(p.children[c-'a']==null){ p.children[c-'a'] = new TrieNode(c); } p = p.children[c-'a']; } p.isLeaf = true; } public StreamChecker(String[] words) { root = new TrieNode('A'); for(String word : words) build(word); que.add(root); } public boolean query(char letter) { boolean isLeaf = false; int sz = que.size(); for(int i=0; i<sz; ++i){ TrieNode node = que.poll(); if(node.children[letter-'a']!=null){ TrieNode next = node.children[letter-'a']; if(next.isLeaf) isLeaf = true; que.add(next); } if(node.ch == 'A') que.add(node); } return isLeaf; } } /** * Your StreamChecker object will be instantiated and called as such: * StreamChecker obj = new StreamChecker(words); * boolean param_1 = obj.query(letter); */