Description
Given many words, words[i] has weight i.
Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.
Examples:
Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1
Note:
-
wordshas length in range[1, 15000]. - For each test case, up to
words.lengthqueriesWordFilter.fmay be made. -
words[i]has length in range[1, 10]. -
prefix, suffixhave lengths in range[0, 10]. -
words[i]andprefix, suffixqueries consist of lowercase letters only.
Solution
Prefix tree and Suffix tree, time O(nk) + O(q * (n + k)), space O(nk)
n: words length
k: max word length
q: f query count
class WordFilter {
private Trie prefixTrie;
private Trie suffixTrie;
public WordFilter(String[] words) {
prefixTrie = new Trie();
suffixTrie = new Trie();
for (int i = 0; i < words.length; ++i) {
String word = words[i];
// build prefix trie
Trie curr = prefixTrie;
for (int j = 0; j < word.length(); ++j) {
int k = word.charAt(j) - 'a';
if (curr.children[k] == null) {
curr.children[k] = new Trie();
}
curr = curr.children[k];
}
curr.isWord = true;
curr.weight = i;
// build suffix trie
curr = suffixTrie;
for (int j = word.length() - 1; j >= 0; --j) {
int k = word.charAt(j) - 'a';
if (curr.children[k] == null) {
curr.children[k] = new Trie();
}
curr = curr.children[k];
}
curr.isWord = true;
curr.weight = i;
}
}
public int f(String prefix, String suffix) {
PriorityQueue<Integer> prefixQueue = new PriorityQueue<>((a, b) -> (b - a));
PriorityQueue<Integer> suffixQueue = new PriorityQueue<>((a, b) -> (b - a));
getWords(prefixTrie, prefix, prefixQueue);
getWords(suffixTrie, new StringBuilder(suffix).reverse().toString(), suffixQueue);
// get the largest common element of two priorityQueue
while (!prefixQueue.isEmpty() && !suffixQueue.isEmpty()) {
if (prefixQueue.peek() > suffixQueue.peek()) {
prefixQueue.poll();
} else if (prefixQueue.peek() < suffixQueue.peek()) {
suffixQueue.poll();
} else {
return prefixQueue.poll();
}
}
return -1;
}
public void getWords(Trie root, String s, PriorityQueue<Integer> queue) {
for (int i = 0; i < s.length() && root != null; ++i) {
root = root.children[s.charAt(i) - 'a'];
}
if (root == null) {
return;
}
getWords(root, queue);
}
public void getWords(Trie root, PriorityQueue<Integer> queue) {
if (root.isWord) { // add root first!
queue.offer(root.weight);
}
for (int i = 0; i < root.children.length; ++i) {
if (root.children[i] == null) {
continue;
}
getWords(root.children[i], queue);
}
}
class Trie {
Trie[] children;
int weight;
boolean isWord;
public Trie() {
children = new Trie[26];
}
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(prefix,suffix);
*/
Two Tries, store information in parent node, time O(nk) + O(q * (n + k)), space O(nk)
由于f函数会被多次调用，每次都找到某个prefix下的所有节点太耗时了，我们可以将子节点的信息存储在从根到它路径上的所有父节点中，这样只需要找到prefix到达的那个节点，就知道它的子节点的weights了。
下面这种写法竟然TLE也是醉醉的，理论上应该比第一种解法快很多啊...WordFilter的初始化会慢一些（因为增加了set操作），但是f方法会快，不过看样子也快不了多少，因为总的words count就不太多。
class WordFilter {
private Trie prefixTrie;
private Trie suffixTrie;
public WordFilter(String[] words) {
prefixTrie = new Trie();
suffixTrie = new Trie();
for (int i = 0; i < words.length; ++i) {
String word = words[i];
// build prefix trie
Trie curr = prefixTrie;
curr.weights.add(i);
for (int j = 0; j < word.length(); ++j) {
int k = word.charAt(j) - 'a';
if (curr.children[k] == null) {
curr.children[k] = new Trie();
}
curr = curr.children[k];
curr.weights.add(i);
}
// build suffix trie
curr = suffixTrie;
curr.weights.add(i);
for (int j = word.length() - 1; j >= 0; --j) {
int k = word.charAt(j) - 'a';
if (curr.children[k] == null) {
curr.children[k] = new Trie();
}
curr = curr.children[k];
curr.weights.add(i);
}
}
}
public int f(String prefix, String suffix) {
Set<Integer> prefixWeights = findWeights(prefixTrie, prefix);
Set<Integer> suffixWeights = findWeights(suffixTrie, new StringBuilder(suffix).reverse().toString());
int maxWeight = -1;
for (int weight : prefixWeights) {
if (suffixWeights.contains(weight) && maxWeight < weight) {
maxWeight = weight;
}
}
return maxWeight;
}
public Set<Integer> findWeights(Trie root, String s) {
for (int i = 0; i < s.length() && root != null; ++i) {
root = root.children[s.charAt(i) - 'a'];
}
return root == null ? Collections.EMPTY_SET : root.weights;
}
class Trie {
Trie[] children;
Set<Integer> weights;
public Trie() {
children = new Trie[26];
weights = new HashSet<>();
}
}
}
/**
* Your WordFilter object will be instantiated and called as such:
* WordFilter obj = new WordFilter(words);
* int param_1 = obj.f(prefix,suffix);
*/
Trie of Suffix Wrapped Words
Consider the word 'apple'. For each suffix of the word, we could insert that suffix, followed by '#', followed by the word, all into the trie.
For example, we will insert '#apple', 'e#apple', 'le#apple', 'ple#apple', 'pple#apple', 'apple#apple' into the trie. Then for a query like prefix = "ap", suffix = "le", we can find it by querying our trie for le#ap.
Complexity Analysis
Time Complexity: O(NK^2 + QK) where N is the number of words, K is the maximum length of a word, and Q is the number of queries.
Space Complexity: O(NK^2), the size of the trie.
class WordFilter {
TrieNode trie;
public WordFilter(String[] words) {
trie = new TrieNode();
for (int weight = 0; weight < words.length; ++weight) {
String word = words[weight] + "{";
for (int i = 0; i < word.length(); ++i) {
TrieNode cur = trie;
cur.weight = weight;
for (int j = i; j < 2 * word.length() - 1; ++j) {
int k = word.charAt(j % word.length()) - 'a';
if (cur.children[k] == null)
cur.children[k] = new TrieNode();
cur = cur.children[k];
cur.weight = weight;
}
}
}
}
public int f(String prefix, String suffix) {
TrieNode cur = trie;
for (char letter: (suffix + '{' + prefix).toCharArray()) {
if (cur.children[letter - 'a'] == null) return -1;
cur = cur.children[letter - 'a'];
}
return cur.weight;
}
}
class TrieNode {
TrieNode[] children;
int weight;
public TrieNode() {
children = new TrieNode[27];
weight = 0;
}
}
