2025-12-10：相鄰字符串之間的最長公共前綴。用go語言，給定一個字符串數組 words。對每個下標 i（0 到 words.length-1）按下面步驟處理並求得一個整數值：
- 把數組中索引為 i 的元素刪掉，得到一個長度為 n-1 的新數組（若原數組長度為 n）。
- 在新數組中，把相鄰的元素兩兩配對（即第 k 個和第 k+1 個），計算每一對從開頭起相同的最長連續字符段的長度。
- 在所有這些相鄰對中取最大的那個長度作為該次刪除的結果。如果刪除後數組中沒有相鄰對（比如原來只有一個元素），或者所有相鄰對的共同起始字符長度都是 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 進行如下處理：
- 計算“跨越”刪除點的LCP：
- 情況：當刪除的位置
i不是數組的頭或尾（即0 < i < n-1）時，刪除操作會使得原本不相鄰的words[i-1]和words[i+1]變成新數組中的一對相鄰字符串。 - 操作：調用
lcp函數計算words[i-1]和words[i+1]的LCP長度，記為l。這個值代表了刪除words[i]後新產生的一對相鄰字符串的公共前綴長度。
- 判斷全局最大LCP是否受影響：
- 核心邏輯：刪除位置
i後，原始數組中的最大LCP (mx1) 能否在新數組中保留，取決於刪除操作是否破壞了構成這個最大LCP的相鄰對（即位於i1和i1+1的那一對）。 - 不受影響的情況：如果被刪除的元素
i既不等於i1也不等於i1+1，那麼原始的最大LCP對在新數組中依然完整存在。因此，新數組的最大LCP可能值就是mx1和新產生的“跨越”LCPl之間的較大者。 - 受影響的情況：如果被刪除的元素
i正好是i1或i1+1，那麼原始的最大LCP對就被破壞了。此時，新數組的最大LCP只能從原始的次大LCP (mx2) 和新產生的“跨越”LCPl之間取較大值。
- 存儲結果：
- 將上面判斷得到的結果（
max(mx1, l)或max(mx2, l)）存入結果數組ans的第i個位置。
第三步：輸出最終結果
完成對所有下標 i 的遍歷後，結果數組 ans 就已經填充完畢，其中 ans[i] 就是刪除第 i 個元素後得到的新數組中所有相鄰對的最大LCP長度。最後，將這個結果數組輸出。
⏱️ 複雜度分析
時間複雜度：O(L)
L的定義：L代表所有字符串長度的總和（題目中給出L <= 100000）。- 分析：
- 第一步預處理需要遍歷所有相鄰對，並對每一對進行LCP比較。最壞情況下，需要比較所有字符串的每一個字符，但字符比較的總次數不會超過所有字符串的長度總和
L。 - 第二步對於每個刪除下標
i（共有n個），最多隻進行一次額外的LCP計算（即計算“跨越”對的LCP）。同樣，這些計算所涉及的字符比較總數也不會超過L。
- 結論：整個算法的時間複雜度與字符串總長度
L呈線性關係，為 O(L)。
空間複雜度：O(n)
- 分析：
- 算法除了輸入數組外，主要額外空間用於存儲結果數組
ans，其大小與輸入數組長度n成正比。 - 預處理階段只用了幾個整型變量（
mx1,mx2,i1）來記錄關鍵信息。 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
} else if l > mx2 {
mx2 = l
}
}
ans := make([]int, n)
for i := range n {
l := 0
if 0 < 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
if 0 < 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(const string& s, const string& 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;
} else if (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;
return 0;
}
