2025-12-10：相邻字符串之间的最长公共前缀。用go语言，给定一个字符串数组 words。对每个下标 i（0 到 word

福大大架构师每日一题

发布于 2025-12-19 09:51:17

2020

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-12-10：相邻字符串之间的最长公共前缀。用go语言，给定一个字符串数组 words。对每个下标 i（0 到 words.length-1）按下面步骤处理并求得一个整数值：

1. 把数组中索引为 i 的元素删掉，得到一个长度为 n-1 的新数组（若原数组长度为 n）。
2. 在新数组中，把相邻的元素两两配对（即第 k 个和第 k+1 个），计算每一对从开头起相同的最长连续字符段的长度。
3. 在所有这些相邻对中取最大的那个长度作为该次删除的结果。如果删除后数组中没有相邻对（比如原来只有一个元素），或者所有相邻对的共同起始字符长度都是 0，则结果记为 0。

最终返回一个与原数组同样长度的整数数组 answer，其中 answer[i] 表示删除第 i 个元素后相邻对之间最大的“从头开始相同的连续前缀”的长度。

说明：字符串的前缀指的是从字符串开头连续截取的一段字符。

1 <= words.length <= 100000。

1 <= words[i].length <= 10000。

words[i] 仅由小写英文字母组成。

words[i] 的长度总和不超过 100000。

输入： 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）

题目来自力扣3598。

🔍 核心思路与步骤分解

第一步：预处理相邻字符串的公共前缀长度

首先，代码需要知道原始数组中每一对相邻字符串的最长公共前缀（LCP）长度。这是后续所有计算的基础。

• 操作：遍历整个 words 数组，从第一个元素到倒数第二个元素，依次计算 words[i] 和 words[i+1] 的LCP长度。计算工作由辅助函数 lcp(s, t string) int 完成。
• lcp函数的工作方式：该函数比较两个字符串，从第一个字符开始逐个比对，直到遇到不同的字符或其中一个字符串结束。返回匹配的字符数量。
• 结果存储：这些计算出的相邻对的LCP长度本身并不显式存储在一个数组里，但代码会在遍历过程中找出其中最大值 (mx1) 和次大值 (mx2)，并记录最大值所在的位置 i1（即第 i1 和 i1+1 个字符串组成的对拥有最长的LCP）。这一步非常关键，因为删除一个元素是否会影响到全局最大的LCP，取决于是否删除了构成这个最大LCP的那一对字符串中的某一个。

第二步：处理每个删除位置 `i`

接下来，代码需要模拟删除数组中每一个位置 i 的元素，并计算新数组中相邻对的最大LCP。它通过一个循环，对每个下标 i 进行如下处理：

1. 计算“跨越”删除点的LCP：
- • 情况：当删除的位置 i 不是数组的头或尾（即 0 < i < n-1）时，删除操作会使得原本不相邻的 words[i-1] 和 words[i+1] 变成新数组中的一对相邻字符串。
- • 操作：调用 lcp 函数计算 words[i-1] 和 words[i+1] 的LCP长度，记为 l。这个值代表了删除 words[i] 后新产生的一对相邻字符串的公共前缀长度。
2. 判断全局最大LCP是否受影响：
- • 核心逻辑：删除位置 i 后，原始数组中的最大LCP (mx1) 能否在新数组中保留，取决于删除操作是否破坏了构成这个最大LCP的相邻对（即位于 i1 和 i1+1 的那一对）。
- • 不受影响的情况：如果被删除的元素 i 既不等于 i1 也不等于 i1+1，那么原始的最大LCP对在新数组中依然完整存在。因此，新数组的最大LCP可能值就是 mx1 和新产生的“跨越”LCP l 之间的较大者。
- • 受影响的情况：如果被删除的元素 i 正好是 i1 或 i1+1，那么原始的最大LCP对就被破坏了。此时，新数组的最大LCP只能从原始的次大LCP (mx2) 和新产生的“跨越”LCP l 之间取较大值。
3. 存储结果：
- • 将上面判断得到的结果（max(mx1, l) 或 max(mx2, l)）存入结果数组 ans 的第 i 个位置。

第三步：输出最终结果

完成对所有下标 i 的遍历后，结果数组 ans 就已经填充完毕，其中 ans[i] 就是删除第 i 个元素后得到的新数组中所有相邻对的最大LCP长度。最后，将这个结果数组输出。

⏱️ 复杂度分析

时间复杂度：O(L)

• L 的定义：L 代表所有字符串长度的总和（题目中给出 L <= 100000）。
• 分析：
1. 1. 第一步预处理需要遍历所有相邻对，并对每一对进行LCP比较。最坏情况下，需要比较所有字符串的每一个字符，但字符比较的总次数不会超过所有字符串的长度总和 L。
2. 2. 第二步对于每个删除下标 i（共有 n 个），最多只进行一次额外的LCP计算（即计算“跨越”对的LCP）。同样，这些计算所涉及的字符比较总数也不会超过 L。
• 结论：整个算法的时间复杂度与字符串总长度 L 呈线性关系，为 O(L)。

空间复杂度：O(n)

• 分析：
1. 1. 算法除了输入数组外，主要额外空间用于存储结果数组 ans，其大小与输入数组长度 n 成正比。
2. 2. 预处理阶段只用了几个整型变量（mx1, mx2, i1）来记录关键信息。
3. 3. lcp 函数等操作只使用了常数级别的临时空间。
• 结论：算法的额外空间消耗主要来自于结果数组，因此空间复杂度为 O(n)。

希望这个分步解释能帮助你清晰地理解整个算法的流程和性能表现。

Go完整代码如下：

package main

import (
    "fmt"
)

func lcp(s, t string)int {
    n := min(len(s), len(t))
    for i := range n {
        if s[i] != t[i] {
            return i
        }
    }
    return n
}

func longestCommonPrefix(words []string) []int {
    n := len(words)
    mx1, mx2, i1 := -1, -1, -2
    for i := range n - 1 {
        l := lcp(words[i], words[i+1])
        if l > mx1 {
            mx2 = mx1
            mx1, i1 = l, i
        } elseif l > mx2 {
            mx2 = l
        }
    }

    ans := make([]int, n)
    for i := range n {
        l := 0
        if0 < i && i < n-1 {
            l = lcp(words[i-1], words[i+1])
        }
        if i != i1 && i != i1+1 { // 最大 LCP 没被破坏
            ans[i] = max(mx1, l)
        } else {
            ans[i] = max(mx2, l)
        }
    }
    return ans
}

func main() {
    words := []string{"jump", "run", "run", "jump", "run"}
    result := longestCommonPrefix(words)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def lcp(s: str, t: str) -> int:
    """返回两个字符串的最长公共前缀长度"""
    n = min(len(s), len(t))
    for i in range(n):
        if s[i] != t[i]:
            return i
    return n

def longestCommonPrefix(words: List[str]) -> List[int]:
    n = len(words)
    mx1, mx2, i1 = -1, -1, -2
    
    # 找出相邻单词间的最大和次大LCP
    for i in range(n - 1):
        l = lcp(words[i], words[i + 1])
        if l > mx1:
            mx2 = mx1
            mx1, i1 = l, i
        elif l > mx2:
            mx2 = l
    
    ans = [0] * n
    for i in range(n):
        # 计算删除当前单词后的可能LCP
        l = 0
        if0 < i < n - 1:
            l = lcp(words[i - 1], words[i + 1])
        
        # 如果当前索引不在最大LCP对应的相邻索引中，则最大LCP仍可用
        if i != i1 and i != i1 + 1:
            ans[i] = max(mx1, l)
        else:
            ans[i] = max(mx2, l)
    
    return ans

if __name__ == "__main__":
    words = ["jump", "run", "run", "jump", "run"]
    result = longestCommonPrefix(words)
    print(result)  # 输出: [0, 3, 3, 0, 3]

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int lcp(conststring& s, conststring& t) {
    int n = min(s.length(), t.length());
    for (int i = 0; i < n; i++) {
        if (s[i] != t[i]) {
            return i;
        }
    }
    return n;
}

vector<int> longestCommonPrefix(const vector<string>& words) {
    int n = words.size();
    int mx1 = -1, mx2 = -1, i1 = -2;

    // 找出相邻单词间的最大和次大LCP
    for (int i = 0; i < n - 1; i++) {
        int l = lcp(words[i], words[i + 1]);
        if (l > mx1) {
            mx2 = mx1;
            mx1 = l;
            i1 = i;
        } elseif (l > mx2) {
            mx2 = l;
        }
    }

    vector<int> ans(n, 0);
    for (int i = 0; i < n; i++) {
        int l = 0;
        if (0 < i && i < n - 1) {
            l = lcp(words[i - 1], words[i + 1]);
        }

        if (i != i1 && i != i1 + 1) {
            ans[i] = max(mx1, l);
        } else {
            ans[i] = max(mx2, l);
        }
    }

    return ans;
}

int main() {
    vector<string> words = {"jump", "run", "run", "jump", "run"};
    vector<int> result = longestCommonPrefix(words);

    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << ", ";
        }
    }
    cout << "]" << endl;

    return0;
}