题目描述
给你一个字符串数组 words，对于范围 [0, words.length - 1] 内的每个下标 i，执行以下步骤：
- 从
words 数组中移除下标 i 处的元素。
- 计算修改后的数组中所有 相邻对 之间的 最长公共前缀 的长度。
返回一个数组 answer，其中 answer[i] 是移除下标 i 后，相邻对之间最长公共前缀的长度。如果 不存在 相邻对，或者 不存在 公共前缀，则 answer[i] 应为 0。
字符串的前缀是从字符串的开头开始延伸到任意位置的子字符串。
示例 1：
输入： words = ["jump","run","run","jump","run"]
输出： [3,0,0,3,3]
解释：
- 移除下标 0：
words 变为 ["run", "run", "jump", "run"]- 最长的相邻对是
["run", "run"]，其公共前缀为 "run"（长度为 3）
- 移除下标 1：
words 变为 ["jump", "run", "jump", "run"]- 没有相邻对有公共前缀（长度为 0）
- 移除下标 2：
words 变为 ["jump", "run", "jump", "run"]- 没有相邻对有公共前缀（长度为 0）
- 移除下标 3：
words 变为 ["jump", "run", "run", "run"]- 最长的相邻对是
["run", "run"]，其公共前缀为 "run"（长度为 3）
- 移除下标 4：
words 变为 ["jump", "run", "run", "jump"]- 最长的相邻对是
["run", "run"]，其公共前缀为 "run"（长度为 3）
示例 2：
输入： words = ["dog","racer","car"]
输出： [0,0,0]
解释：
提示：
1 <= words.length <= 1051 <= words[i].length <= 104words[i] 仅由小写英文字母组成。words[i] 的长度总和不超过 105。
解法
方法一：有序集合
我们定义一个函数 \(\textit{calc}(s, t)\)，它计算字符串 \(s\) 和 \(t\) 的最长公共前缀的长度。我们可以使用有序集合来维护所有相邻字符串对的最长公共前缀长度。
定义一个函数 \(\textit{add}(i, j)\)，它将下标 \(i\) 和 \(j\) 处的字符串对的最长公共前缀长度添加到有序集合中。定义一个函数 \(\textit{remove}(i, j)\)，它从有序集合中移除下标 \(i\) 和 \(j\) 处的字符串对的最长公共前缀长度。
我们首先计算所有相邻字符串对的最长公共前缀长度，并将其存储在有序集合中。然后，我们遍历每个下标 \(i\)，执行以下操作：
- 移除下标 \(i\) 和 \(i + 1\) 处的字符串对的最长公共前缀长度。
- 移除下标 \(i - 1\) 和 \(i\) 处的字符串对的最长公共前缀长度。
- 添加下标 \(i - 1\) 和 \(i + 1\) 处的字符串对的最长公共前缀长度。
- 将当前有序集合中的最大值（如果存在且大于 0）添加到答案中。
- 移除下标 \(i - 1\) 和 \(i + 1\) 处的字符串对的最长公共前缀长度。
- 添加下标 \(i - 1\) 和 \(i\) 处的字符串对的最长公共前缀长度。
- 添加下标 \(i\) 和 \(i + 1\) 处的字符串对的最长公共前缀长度。
这样，我们可以在每次移除一个字符串后，快速计算出相邻字符串对的最长公共前缀长度。
时间复杂度 \(O(L + n \times \log n)\)，空间复杂度 \(O(n)\)，其中 \(L\) 是所有字符串的总长度，而 \(n\) 是字符串的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution:
def longestCommonPrefix(self, words: List[str]) -> List[int]:
@cache
def calc(s: str, t: str) -> int:
k = 0
for a, b in zip(s, t):
if a != b:
break
k += 1
return k
def add(i: int, j: int):
if 0 <= i < n and 0 <= j < n:
sl.add(calc(words[i], words[j]))
def remove(i: int, j: int):
if 0 <= i < n and 0 <= j < n:
sl.remove(calc(words[i], words[j]))
n = len(words)
sl = SortedList(calc(a, b) for a, b in pairwise(words))
ans = []
for i in range(n):
remove(i, i + 1)
remove(i - 1, i)
add(i - 1, i + 1)
ans.append(sl[-1] if sl and sl[-1] > 0 else 0)
remove(i - 1, i + 1)
add(i - 1, i)
add(i, i + 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 | class Solution {
private final TreeMap<Integer, Integer> tm = new TreeMap<>();
private String[] words;
private int n;
public int[] longestCommonPrefix(String[] words) {
n = words.length;
this.words = words;
for (int i = 0; i + 1 < n; ++i) {
tm.merge(calc(words[i], words[i + 1]), 1, Integer::sum);
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
remove(i, i + 1);
remove(i - 1, i);
add(i - 1, i + 1);
ans[i] = !tm.isEmpty() && tm.lastKey() > 0 ? tm.lastKey() : 0;
remove(i - 1, i + 1);
add(i - 1, i);
add(i, i + 1);
}
return ans;
}
private void add(int i, int j) {
if (i >= 0 && i < n && j >= 0 && j < n) {
tm.merge(calc(words[i], words[j]), 1, Integer::sum);
}
}
private void remove(int i, int j) {
if (i >= 0 && i < n && j >= 0 && j < n) {
int x = calc(words[i], words[j]);
if (tm.merge(x, -1, Integer::sum) == 0) {
tm.remove(x);
}
}
}
private int calc(String s, String t) {
int m = Math.min(s.length(), t.length());
for (int k = 0; k < m; ++k) {
if (s.charAt(k) != t.charAt(k)) {
return k;
}
}
return m;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | class Solution {
public:
vector<int> longestCommonPrefix(vector<string>& words) {
multiset<int> ms;
int n = words.size();
auto calc = [&](const string& s, const string& t) {
int m = min(s.size(), t.size());
for (int k = 0; k < m; ++k) {
if (s[k] != t[k]) {
return k;
}
}
return m;
};
for (int i = 0; i + 1 < n; ++i) {
ms.insert(calc(words[i], words[i + 1]));
}
vector<int> ans(n);
auto add = [&](int i, int j) {
if (i >= 0 && i < n && j >= 0 && j < n) {
ms.insert(calc(words[i], words[j]));
}
};
auto remove = [&](int i, int j) {
if (i >= 0 && i < n && j >= 0 && j < n) {
int x = calc(words[i], words[j]);
auto it = ms.find(x);
if (it != ms.end()) {
ms.erase(it);
}
}
};
for (int i = 0; i < n; ++i) {
remove(i, i + 1);
remove(i - 1, i);
add(i - 1, i + 1);
ans[i] = ms.empty() ? 0 : *ms.rbegin();
remove(i - 1, i + 1);
add(i - 1, i);
add(i, i + 1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | func longestCommonPrefix(words []string) []int {
n := len(words)
tm := treemap.NewWithIntComparator()
calc := func(s, t string) int {
m := min(len(s), len(t))
for k := 0; k < m; k++ {
if s[k] != t[k] {
return k
}
}
return m
}
add := func(i, j int) {
if i >= 0 && i < n && j >= 0 && j < n {
x := calc(words[i], words[j])
if v, ok := tm.Get(x); ok {
tm.Put(x, v.(int)+1)
} else {
tm.Put(x, 1)
}
}
}
remove := func(i, j int) {
if i >= 0 && i < n && j >= 0 && j < n {
x := calc(words[i], words[j])
if v, ok := tm.Get(x); ok {
if v.(int) == 1 {
tm.Remove(x)
} else {
tm.Put(x, v.(int)-1)
}
}
}
}
for i := 0; i+1 < n; i++ {
add(i, i+1)
}
ans := make([]int, n)
for i := 0; i < n; i++ {
remove(i, i+1)
remove(i-1, i)
add(i-1, i+1)
if !tm.Empty() {
if maxKey, _ := tm.Max(); maxKey.(int) > 0 {
ans[i] = maxKey.(int)
}
}
remove(i-1, i+1)
add(i-1, i)
add(i, i+1)
}
return ans
}
|