智谱清言 LeetCode 2573. 找出对应 LCP 矩阵的字符串 Python3实现
LeetCode 2573. 找出对应 LCP 矩阵的字符串
思路分析
LCP 矩阵定义：lcp[i][j] 表示字符串 s 从位置 i 和位置 j 开始的最长公共前缀长度。
核心观察：LCP 矩阵具有递推性质：
若 lcp[i][j] > 0，则 lcp[i+1][j+1] = lcp[i][j] - 1（因为去掉首字符后，公共前缀长度减1）
若 s[i] == s[j]，则 lcp[i][j] = lcp[i+1][j+1] + 1；否则 lcp[i][j] = 0
算法步骤：
验证：检查 lcp 矩阵的对称性、对角线值、递推关系是否满足
构造：从后往前，利用 lcp[i][j] > 0 ⇒ s[i] == s[j] 来等价分组，贪心赋最小字符
校验：用构造出的字符串重新计算 LCP 矩阵，与输入比对
Python3 实现
class Solution:
def findTheString(self, lcp: List[List[int]]) -> str:
n = len(lcp)
# ========== 第一步：验证 LCP 矩阵的基本性质 ==========
for i in range(n):
for j in range(n):
# 对角线上 lcp[i][i] = n - i
if i == j and lcp[i][i] != n - i:
return “”
# 矩阵必须对称
if lcp[i][j] != lcp[j][i]:
return “”
# lcp 值不能越界
if lcp[i][j] > n - max(i, j):
return “”
# 递推性质：lcp[i][j] > 0 时，lcp[i+1][j+1] = lcp[i][j] - 1
if i < n - 1 and j < n - 1:
if lcp[i][j] > 0 and lcp[i + 1][j + 1] != lcp[i][j] - 1:
return “”
# ========== 第二步：贪心构造字典序最小的字符串 ==========
# 核心关系：lcp[i][j] > 0 ⟹ s[i] == s[j]
# 用并查集（或直接标记）将 s[i] == s[j] 的位置分组
s = [‘’] * n
c = ord(‘a’) # 当前可用的最小字符
for i in range(n):
if s[i]: # 已被前面的位置标记过
continue
if c > ord(‘z’): # 超出 26 个字母，无法构造
return “”
# 将所有与 i 应该相同的字符位置标记为同一字符
s[i] = chr©
for j in range(i + 1, n):
if not s[j] and lcp[i][j] > 0:
s[j] = chr©
c += 1 # 下一个位置用下一个字母
result = ‘’.join(s)
# ========== 第三步：用构造的字符串重新计算 LCP，验证一致性 ==========
# 从右下角向左上角递推计算
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if result[i] == result[j]:
dp[i][j] = (1 + dp[i + 1][j + 1]) if (i < n - 1 and j < n - 1) else 1
else:
dp[i][j] = 0
for i in range(n):
for j in range(n):
if dp[i][j] != lcp[i][j]:
return “”
return result
关键点解释
步骤 说明
性质验证 检查对称性 lcp[i][j]==lcp[j][i]、对角线 lcp[i][i]==n-i、递推 lcp[i+1][j+1]==lcp[i][j]-1 (当lcp[i][j]>0)、边界 lcp[i][j]<=n-max(i,j)
贪心构造 遍历每个位置 i，若未赋值则分配当前最小字符 c，然后将所有 lcp[i][j]>0 的位置 j 也赋为 c（因为 lcp[i][j]>0 ⟹ s[i]==s[j]）
一致性校验 用构造出的字符串重新递推计算 LCP 矩阵，与输入比对——这一步捕获"该不等但 lcp>0"的反例（例如 lcp[0][1]=0 但构造出 s[0]s[1]‘a’）
复杂度
时间：O(n²) — 三次遍历 n×n 矩阵
空间：O(n²) — 存储验证用的 dp 矩阵