Medium

题目描述

给你一个字符串数组 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]
解释：移除任何索引的结果都是 0。

约束条件：

  • 1 <= words.length <= 10^5
  • 1 <= words[i].length <= 10^4
  • words[i] 由小写英文字母组成
  • words[i].length 的总和小于等于 10^5

解题思路

解题思路

这道题的关键在于高效地处理删除元素后的最长公共前缀计算。直接暴力模拟每次删除会导致时间复杂度过高。

核心思路：预计算 + 动态规划

  1. 预计算相邻对的公共前缀长度：首先计算原数组中每对相邻字符串的最长公共前缀长度。

  2. 前缀最大值数组：对于每个位置 i，计算从位置 0 到位置 i 的相邻对中最长公共前缀的最大值。

  3. 后缀最大值数组：对于每个位置 i，计算从位置 i 到数组末尾的相邻对中最长公共前缀的最大值。

  4. 处理删除操作：当删除位置 i 的元素时，新的相邻对包括：

    • 原来位置 i 之前的所有相邻对（使用前缀最大值）
    • 原来位置 i 之后的所有相邻对（使用后缀最大值）
    • 如果存在 words[i-1] 和 words[i+1]，它们会成为新的相邻对

  5. 边界处理：特别注意数组长度小于等于2的情况，删除后可能没有相邻对。

时间复杂度优化：通过预计算避免了重复计算公共前缀，将整体复杂度从 O(n²×m) 降低到 O(n×m)，其中 n 是数组长度，m 是平均字符串长度。

代码实现

class Solution {
public:
    vector<int> longestCommonPrefix(vector<string>& words) {
        int n = words.size();
        vector<int> answer(n, 0);
        
        if (n <= 1) return answer;
        
        // 计算相邻字符串的公共前缀长度
        auto getCommonPrefixLength = [](const string& a, const string& b) {
            int len = 0;
            int minLen = min(a.length(), b.length());
            while (len < minLen && a[len] == b[len]) {
                len++;
            }
            return len;
        };
        
        // 预计算所有相邻对的公共前缀长度
        vector<int> adjacent(n - 1);
        for (int i = 0; i < n - 1; i++) {
            adjacent[i] = getCommonPrefixLength(words[i], words[i + 1]);
        }
        
        // 计算前缀最大值
        vector<int> prefixMax(n - 1, 0);
        if (n > 1) {
            prefixMax[0] = adjacent[0];
            for (int i = 1; i < n - 1; i++) {
                prefixMax[i] = max(prefixMax[i - 1], adjacent[i]);
            }
        }
        
        // 计算后缀最大值
        vector<int> suffixMax(n - 1, 0);
        if (n > 1) {
            suffixMax[n - 2] = adjacent[n - 2];
            for (int i = n - 3; i >= 0; i--) {
                suffixMax[i] = max(suffixMax[i + 1], adjacent[i]);
            }
        }
        
        // 计算每个删除操作的结果
        for (int i = 0; i < n; i++) {
            int maxPrefix = 0;
            
            // 前面的相邻对
            if (i > 1) {
                maxPrefix = max(maxPrefix, prefixMax[i - 2]);
            }
            
            // 后面的相邻对
            if (i < n - 2) {
                maxPrefix = max(maxPrefix, suffixMax[i + 1]);
            }
            
            // 新形成的相邻对 (i-1, i+1)
            if (i > 0 && i < n - 1) {
                int newPairPrefix = getCommonPrefixLength(words[i - 1], words[i + 1]);
                maxPrefix = max(maxPrefix, newPairPrefix);
            }
            
            answer[i] = maxPrefix;
        }
        
        return answer;
    }
};

class Solution:
    def longestCommonPrefix(self, words: List[str]) -> List[int]:
        n = len(words)
        answer = [0] * n
        
        if n <= 1:
            return answer
        
        def get_common_prefix_length(a, b):
            length = 0
            min_len = min(len(a), len(b))
            while length < min_len and a[length] == b[length]:
                length += 1
            return length
        
        # 预计算所有相邻对的公共前缀长度
        adjacent = []
        for i in range(n - 1):
            adjacent.append(get_common_prefix_length(words[i], words[i + 1]))
        
        # 计算前缀最大值
        prefix_max = [0] * (n - 1)
        if n > 1:
            prefix_max[0] = adjacent[0]
            for i in range(1, n - 1):
                prefix_max[i] = max(prefix_max[i - 1], adjacent[i])
        
        # 计算后缀最大值
        suffix_max = [0] * (n - 1)
        if n > 1:
            suffix_max[n - 2] = adjacent[n - 2]
            for i in range(n - 3, -1, -1):
                suffix_max[i] = max(suffix_max[i + 1], adjacent[i])
        
        # 计算每个删除操作的结果
        for i in range(n):
            max_prefix = 0
            
            # 前面的相邻对
            if i > 1:
                max_prefix = max(max_prefix, prefix_max[i - 2])
            
            # 后面的相邻对
            if i < n - 2:
                max_prefix = max(max_prefix, suffix_max[i + 1])
            
            # 新形成的相邻对 (i-1, i+1)
            if i > 0 and i < n - 1:
                new_pair_prefix = get_common_prefix_length(words[i - 1], words[i + 1])
                max_prefix = max(max_prefix, new_pair_prefix)
            
            answer[i] = max_prefix
        
        return answer

public class Solution {
    public int[] LongestCommonPrefix(string[] words) {
        int n = words.Length;
        int[] answer = new int[n];
        
        if (n <= 1) return answer;
        
        int GetCommonPrefixLength(string a, string b) {
            int length = 0;
            int minLen = Math.Min(a.Length, b.Length);
            while (length < minLen && a[length] == b[length]) {
                length++;
            }
            return length;
        }
        
        // 预计算所有相邻对的公共前缀长度
        int[] adjacent = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            adjacent[i] = GetCommonPrefixLength(words[i], words[i + 1]);
        }
        
        // 计算前缀最大值
        int[] prefixMax = new int[n - 1];
        if (n > 1) {
            prefixMax[0] = adjacent[0];
            for (int i = 1; i < n - 1; i++) {
                prefixMax[i] = Math.Max(prefixMax[i - 1], adjacent[i]);
            }
        }
        
        // 计算后缀最大值
        int[] suffixMax = new int[n - 1];
        if (n > 1) {
            suffixMax[n - 2] = adjacent[n - 2];
            for (int i = n - 3; i >= 0; i--) {
                suffixMax[i] = Math.Max(suffixMax[i + 1], adjacent[i]);
            }
        }
        
        // 计算每个删除操作的结果
        for (int i = 0; i < n; i++) {
            int maxPrefix = 0;
            
            // 前面的相邻对
            if (i > 1) {
                maxPrefix = Math.Max(maxPrefix, prefixMax[i - 2]);
            }
            
            // 后面的相邻对
            if (i < n - 2) {
                maxPrefix = Math.Max(maxPrefix, suffixMax[i + 1]);
            }
            
            // 新形成的相邻对 (i-1, i+1)
            if (i > 0 && i < n - 1) {
                int newPairPrefix = GetCommonPrefixLength(words[i - 1], words[i + 1]);
                maxPrefix = Math.Max(maxPrefix, newPairPrefix);
            }
            
            answer[i] = maxPrefix;
        }
        
        return answer;
    }
}

var longestCommonPrefix = function(words) {
    const n = words.length;
    const answer = new Array(n).fill(0);
    
    if (n <= 1) return answer;
    
    function getCommonPrefixLength(a, b) {
        let length = 0;
        const minLen = Math.min(a.length, b.length);
        while (length < minLen && a[length]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m)，其中 n 是数组长度，m 是平均字符串长度。需要计算所有相邻对的公共前缀，以及处理每次删除操作
空间复杂度O(n)，需要存储相邻对的公共前缀长度、前缀最大值数组、后缀最大值数组和结果数组