3485. 删除元素后 K 个字符串的最长公共前缀
题目描述
给你一个字符串数组 words 和一个整数 k。
对于范围 [0, words.length - 1] 中的每个下标 i，在移除第 i 个元素后的剩余数组中，找到任意 k 个字符串（k 个下标 互不相同）的 最长公共前缀 的 长度。
返回一个数组 answer，其中 answer[i] 是 i 个元素的答案。如果移除第 i 个元素后，数组中的字符串少于 k 个，answer[i] 为 0。
一个字符串的 前缀 是一个从字符串的开头开始并延伸到字符串内任何位置的子字符串。
一个 子字符串 是字符串中一段连续的字符序列。
示例 1：
输入： words = ["jump","run","run","jump","run"], k = 2
输出： [3,4,4,3,4]
解释：
- 移除下标 0 处的元素
"jump"：<ul> <li><code>words</code> 变为： <code>["run", "run", "jump", "run"]</code>。 <code>"run"</code> 出现了 3 次。选择任意两个得到的最长公共前缀是 <code>"run"</code> （长度为 3）。</li> </ul> </li> <li>移除下标 1 处的元素 <code>"run"</code> ： <ul> <li><code>words</code> 变为： <code>["jump", "run", "jump", "run"]</code>。 <code>"jump"</code> 出现了 2 次。选择这两个得到的最长公共前缀是 <code>"jump"</code> （长度为 4）。</li> </ul> </li> <li>移除下标 2 处的元素 <code>"run"</code> ： <ul> <li><code>words</code> 变为： <code>["jump", "run", "jump", "run"]</code>。 <code>"jump"</code> 出现了 2 次。选择这两个得到的最长公共前缀是 <code>"jump"</code> （长度为 4）。</li> </ul> </li> <li>移除下标 3 处的元素 <code>"jump"</code> ： <ul> <li><code>words</code> 变为： <code>["jump", "run", "run", "run"]</code>。 <code>"run"</code> 出现了 3 次。选择任意两个得到的最长公共前缀是 <code>"run"</code> （长度为 3）。</li> </ul> </li> <li>移除下标 4 处的元素 <code>"run"</code> ： <ul> <li><code>words</code> 变为： <code>["jump", "run", "run", "jump"]</code>。 <code>"jump"</code> 出现了 2 次。选择这两个得到的最长公共前缀是 <code>"jump"</code> （长度为 4）。</li> </ul> </li>
示例 2：
输入： words = ["dog","racer","car"], k = 2
输出： [0,0,0]
解释：
- 移除任何元素的结果都是 0。
提示：
1 <= k <= words.length <= 1051 <= words[i].length <= 104words[i]由小写英文字母组成。words[i].length的总和小于等于105。
解法
方法一
Python3
Java
class Solution {
static class TrieNode {
int count = 0;
int depth = 0;
int[] children = new int[26];
TrieNode() {
for (int i = 0; i < 26; ++i) children[i] = -1;
}
}
static class SegmentTree {
int n;
int[] tree;
int[] globalCount;
SegmentTree(int n, int[] globalCount) {
this.n = n;
this.globalCount = globalCount;
this.tree = new int[4 * (n + 1)];
for (int i = 0; i < tree.length; i++) tree[i] = -1;
build(1, 1, n);
}
void build(int idx, int l, int r) {
if (l == r) {
tree[idx] = globalCount[l] > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]);
}
void update(int idx, int l, int r, int pos, int newVal) {
if (l == r) {
tree[idx] = newVal > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
update(idx * 2, l, mid, pos, newVal);
} else {
update(idx * 2 + 1, mid + 1, r, pos, newVal);
}
tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]);
}
int query() {
return tree[1];
}
}
public int[] longestCommonPrefix(String[] words, int k) {
int n = words.length;
int[] ans = new int[n];
if (n - 1 < k) return ans;
ArrayList<TrieNode> trie = new ArrayList<>();
trie.add(new TrieNode());
for (String word : words) {
int cur = 0;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (trie.get(cur).children[idx] == -1) {
trie.get(cur).children[idx] = trie.size();
TrieNode node = new TrieNode();
node.depth = trie.get(cur).depth + 1;
trie.add(node);
}
cur = trie.get(cur).children[idx];
trie.get(cur).count++;
}
}
int maxDepth = 0;
for (int i = 1; i < trie.size(); ++i) {
if (trie.get(i).count >= k) {
maxDepth = Math.max(maxDepth, trie.get(i).depth);
}
}
int[] globalCount = new int[maxDepth + 1];
for (int i = 1; i < trie.size(); ++i) {
TrieNode node = trie.get(i);
if (node.count >= k && node.depth <= maxDepth) {
globalCount[node.depth]++;
}
}
List<List<Integer>> fragileList = new ArrayList<>();
for (int i = 0; i < n; ++i) {
fragileList.add(new ArrayList<>());
}
for (int i = 0; i < n; ++i) {
int cur = 0;
for (char c : words[i].toCharArray()) {
int idx = c - 'a';
cur = trie.get(cur).children[idx];
if (trie.get(cur).count == k) {
fragileList.get(i).add(trie.get(cur).depth);
}
}
}
int segSize = maxDepth;
if (segSize >= 1) {
SegmentTree segTree = new SegmentTree(segSize, globalCount);
for (int i = 0; i < n; ++i) {
if (n - 1 < k) {
ans[i] = 0;
} else {
for (int d : fragileList.get(i)) {
segTree.update(1, 1, segSize, d, globalCount[d] - 1);
}
int res = segTree.query();
ans[i] = res == -1 ? 0 : res;
for (int d : fragileList.get(i)) {
segTree.update(1, 1, segSize, d, globalCount[d]);
}
}
}
}
return ans;
}
}
C++
class Solution {
public:
struct TrieNode {
int count = 0;
int depth = 0;
int children[26] = {0};
};
class SegmentTree {
public:
int n;
vector<int> tree;
vector<int>& globalCount;
SegmentTree(int n, vector<int>& globalCount)
: n(n)
, globalCount(globalCount) {
tree.assign(4 * (n + 1), -1);
build(1, 1, n);
}
void build(int idx, int l, int r) {
if (l == r) {
tree[idx] = globalCount[l] > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
void update(int idx, int l, int r, int pos, int newVal) {
if (l == r) {
tree[idx] = newVal > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(idx * 2, l, mid, pos, newVal);
else
update(idx * 2 + 1, mid + 1, r, pos, newVal);
tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
int query() {
return tree[1];
}
};
vector<int> longestCommonPrefix(vector<string>& words, int k) {
int n = words.size();
vector<int> ans(n, 0);
if (n - 1 < k) return ans;
vector<TrieNode> trie(1);
for (const string& word : words) {
int cur = 0;
for (char c : word) {
int idx = c - 'a';
if (trie[cur].children[idx] == 0) {
trie[cur].children[idx] = trie.size();
trie.push_back({0, trie[cur].depth + 1});
}
cur = trie[cur].children[idx];
trie[cur].count++;
}
}
int maxDepth = 0;
for (int i = 1; i < trie.size(); ++i) {
if (trie[i].count >= k) {
maxDepth = max(maxDepth, trie[i].depth);
}
}
vector<int> globalCount(maxDepth + 1, 0);
for (int i = 1; i < trie.size(); ++i) {
if (trie[i].count >= k && trie[i].depth <= maxDepth) {
globalCount[trie[i].depth]++;
}
}
vector<vector<int>> fragileList(n);
for (int i = 0; i < n; ++i) {
int cur = 0;
for (char c : words[i]) {
int idx = c - 'a';
cur = trie[cur].children[idx];
if (trie[cur].count == k) {
fragileList[i].push_back(trie[cur].depth);
}
}
}
int segSize = maxDepth;
if (segSize >= 1) {
SegmentTree segTree(segSize, globalCount);
for (int i = 0; i < n; ++i) {
if (n - 1 < k) {
ans[i] = 0;
} else {
for (int d : fragileList[i]) {
segTree.update(1, 1, segSize, d, globalCount[d] - 1);
}
int res = segTree.query();
ans[i] = res == -1 ? 0 : res;
for (int d : fragileList[i]) {
segTree.update(1, 1, segSize, d, globalCount[d]);
}
}
}
}
return ans;
}
};
Go