Leetcode 3598. Longest Common Prefix Between Adjacent Strings After Removals

• Leetcode 3598. Longest Common Prefix Between Adjacent Strings After Removals
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3598. Longest Common Prefix Between Adjacent Strings After Removals

1. 解题思路

这一题的话思路上就是一个累计数组的思路。考察任意一个位置$i$上的答案，事实上就是考察$i-1$之前所有相邻字符串的最大值与$i+1$之后所有相邻元素的最大值，以及$i-1$与$i+1$两个字符串的最大值，因此，我们只需要提前算好这些值即可快速求得任意位置上的答案了。

2. 代码实现

给出python代码实现如下：

class Solution:def longestCommonPrefix(self, words: List[str]) -> List[int]:n = len(words)if n == 1:return [0]if len(set(words)) == 1 and n > 2:return [len(words[0]) for _ in range(n)]def count_prefix(w1, w2):if len(w1) > len(w2):return count_prefix(w2, w1)ans = 0for ch1, ch2 in zip(w1, w2):if ch1 != ch2:breakans += 1return ansadj = [count_prefix(words[i], words[i+1]) for i in range(n-1)]left = [0 for _ in range(n)]right = [0 for _ in range(n)]for i in range(n-1):left[i+1] = max(left[i], adj[i])right[n-2-i] = max(right[n-1-i], adj[n-2-i])tri = [count_prefix(words[i-1], words[i+1]) for i in range(1, n-1)]ans = []for i in range(n):if i == 0:m = right[1]elif i == n-1:m = left[n-2]else:m = max(left[i-1], right[i+1])ans.append(max(m, tri[i-1]) if 1 <= i < n-1 else m)return ans

提交代码评测得到：耗时1000ms，占用内存40.39MB。