Problem
Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.
For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.
Implement the StreamChecker class:
・ StreamChecker(String[] words) Initializes the object with the strings array words. ・ boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.Example 1:
Input ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"] [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]] Output [null, false, false, false, true, false, true, false, false, false, false, false, true] Explanation StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]); 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 wordlistConstraints:
・ 1 <= words.length <= 2000 ・ 1 <= words[i].length <= 2000 ・ words[i] consists of lowercase English letters. ・ letter is a lowercase English letter. ・ At most 4 * 10⁴ calls will be made to query.
Idea
String의 prefix 또는 suffix와 관련된 문제를 효율적으로 풀기 위해선 항상 TrieNode를 이용하게 된다.
TrieNode는 노드 별로 알파벳 26개를 자식노드로 가지는 노드다. 문제의 의도에 따라 String의 끝을 표시하는 boolean 값을 추가할 수 있다.
여기서는 StreamChecker라는 클래스를 설계해야 한다. StreamChecker의 생성자에서 instance를 초기화하고, query 함수에서 해당 문자로 끝나는 suffix가 words에 존재하는 지 여부를 리턴해야 한다.
TrieNode는 다음과 같이 설계한다. 해당 노드에서 문자열이 시작되면 isWord를 true로 설정하고 알파벳 26개에 해당하는 TrieNode를 자식 노드 array로 가진다.
StreamChecker의 생성자에서는 words로 주어진 문자들을 이용해 TrieNode를 만든다. 모든 문자열의 시작점이 되는 root node를 먼저 만들고, words의 알파벳을 역순으로 하여 TrieNode를 생성하고 추가한다. words의 첫 문자일 경우 isWord 플래그를 true로 만들어준다. query 함수에 주어진 문자를 추적하기 위해 StringBuilder instance도 만든다.
query 함수는 주어진 문자로 만든 string이 words 문자열 중 하나가 suffix가 되는 지 여부를 리턴한다. 우선 주어진 문자를 StringBuilder에 append시킨다. 시작점이 되는 TrieNode를 root로 설정하고 StringBuilder를 역순으로 탐색한다.
StringBuilder를 역순으로 탐색하면서 해당 문자가 TrieNode에 존재하는지 확인한다. TrieNode가 존재하고 isWord 플래그가 true일 경우 suffix가 되는 것이므로 곧바로 true를 리턴한다.
StringBuilder를 전부 탐색했는데도 true일 조건이 나오지 않거나, 탐색 중 문자가 TrieNode로 존재하지 않을 경우 false를 리턴한다.
바로 풀지는 못 했지만 너무 재미있고 유용한 문제다!
Solution
class StreamChecker {
class TrieNode {
boolean isWord;
TrieNode[] children = new TrieNode[26];
}
StringBuilder sb = new StringBuilder();
TrieNode root = new TrieNode();
public StreamChecker(String[] words) {
createTrie(words);
}
public boolean query(char letter) {
sb.append(letter);
TrieNode node = root;
for (int i=sb.length()-1; i >= 0 && node != null; i--) {
char c = sb.charAt(i);
node = node.children[c - 'a'];
if (node != null && node.isWord)
return true;
}
return false;
}
private void createTrie(String[] words) {
for (String word : words) {
TrieNode node = root;
for (int i=word.length()-1; i >= 0; i--) {
char c = word.charAt(i);
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isWord = true;
}
}
}Reference
