3093. 最长公共后缀查询 - 力扣（LeetCode）
3093. 最长公共后缀查询 - 给你两个字符串数组 wordsContainer 和 wordsQuery 。 对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果...
思路
多亏佬友前几天题目中出现的前缀树算法，用这个答题简单多了。
因为要 最长公共后缀中字符串最短的，多个字符串长度相同时取最最先出现的，所以前缀树的结构要加上 最短长度minLen和 最早出现idx。
然后将 wordsContainer 中的字符串倒序插入到前缀树中，遍历 wordsQuery 用同样的找到最长公共后缀的node，取出idx即可。
代码
class Solution {
private static class TrieNode {
TrieNode[] children = new TrieNode[26];
int idx = Integer.MAX_VALUE;
int minLen = Integer.MAX_VALUE;
}
public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
TrieNode root = new TrieNode();
for (int i = 0; i < wordsContainer.length; i++) {
insert(root, wordsContainer[i], i);
}
int n = wordsQuery.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = query(root, wordsQuery[i]);
}
return ans;
}
private int query(TrieNode node, String str) {
int len = str.length();
for (int i = len - 1; i >= 0; i--) {
int o = str.charAt(i) - 'a';
if (node.children[o] == null) {
return node.idx;
}
node = node.children[o];
}
return node.idx;
}
private void insert(TrieNode node, String str, int idx) {
int len = str.length();
if (node.minLen > len) {
node.minLen = len;
node.idx = idx;
} else if (node.minLen == len && idx < node.idx) {
node.idx = idx;
}
for (int i = len - 1; i >= 0; i--) {
int o = str.charAt(i) - 'a';
if (node.children[o] == null) {
node.children[o] = new TrieNode();
}
node = node.children[o];
if (node.minLen > len) {
node.minLen = len;
node.idx = idx;
} else if (node.minLen == len && idx < node.idx) {
node.idx = idx;
}
}
}
}
1 个帖子 - 1 位参与者
来源: LinuxDo 最新话题查看原文