You are given two arrays of strings wordsContainer and wordsQuery.
For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i]. If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer.
Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].
Example 1:
Input: wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
Output: [1,1,1]
Explanation:
Let's look at each wordsQuery[i] separately:
wordsQuery[0] = "cd", strings from wordsContainer that share the longest common suffix "cd" are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.wordsQuery[1] = "bcd", strings from wordsContainer that share the longest common suffix "bcd" are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.wordsQuery[2] = "xyz", there is no string from wordsContainer that shares a common suffix. Hence the longest common suffix is "", that is shared with strings at index 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.Example 2:
Input: wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
Output: [2,0,2]
Explanation:
Let's look at each wordsQuery[i] separately:
wordsQuery[0] = "gh", strings from wordsContainer that share the longest common suffix "gh" are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.wordsQuery[1] = "acbfgh", only the string at index 0 shares the longest common suffix "fgh". Hence it is the answer, even though the string at index 2 is shorter.wordsQuery[2] = "acbfegh", strings from wordsContainer that share the longest common suffix "gh" are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.
Constraints:
1 <= wordsContainer.length, wordsQuery.length <= 1041 <= wordsContainer[i].length <= 5 * 1031 <= wordsQuery[i].length <= 5 * 103wordsContainer[i] consists only of lowercase English letters.wordsQuery[i] consists only of lowercase English letters.wordsContainer[i].length is at most 5 * 105.wordsQuery[i].length is at most 5 * 105.class Solution {
private class TrieNode {
TrieNode[] children;
int startIdx = -1;
int startLen = -1;
TrieNode(int idx, int len) {
this.children = new TrieNode[26];
this.startIdx = idx;
this.startLen = len;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("\n[");
for (int i = 0; i < 26; i++)
sb.append((char) ('a' + i)).append("=>").append(children[i]).append(",");
sb.append("\tIdx" + startIdx + "\tLen" + startLen + "]\n");
return sb.toString();
}
}
private class Trie {
TrieNode end = new TrieNode(-1, Integer.MAX_VALUE);
int search(String word) {
char[] cs = word.toCharArray();
TrieNode curr = this.end;
for (int i = cs.length - 1; i >= 0; i--) {
TrieNode temp = curr.children[cs[i] - 'a'];
if (temp == null)
return curr.startIdx;
curr = temp;
}
return curr.startIdx;
}
void build(String word, int idx) {
char[] cs = word.toCharArray();
TrieNode curr = this.end;
if (cs.length < curr.startLen) { // update no match ("")
curr.startIdx = idx;
curr.startLen = cs.length;
}
for (int i = cs.length - 1; i >= 0; i--) {
TrieNode temp = curr.children[cs[i] - 'a'];
if (temp == null)
temp = new TrieNode(idx, cs.length);
else if (temp.startLen > cs.length) { // update to shortest string on path
temp.startIdx = idx;
temp.startLen = cs.length;
}
curr = curr.children[cs[i] - 'a'] = temp;
}
}
}
public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
Trie suffixTrie = new Trie();
for (int i = 0; i < wordsContainer.length; i++)
suffixTrie.build(wordsContainer[i], i);
// System.out.println(suffixTrie.end);
int[] ans = new int[wordsQuery.length];
for (int i = 0; i < wordsQuery.length; i++)
ans[i] = suffixTrie.search(wordsQuery[i]);
return ans;
}
}