LeetCode 2573. 找出对应 LCP 矩阵的字符串思路分析LCP 矩阵定义lcp[i][j] 表示字符串 s 从位置 i 和位置 j 开始的最长公共前缀长度。核心观察LCP 矩阵具有递推性质若 lcp[i][j] 0则 lcp[i1][j1] lcp[i][j] - 1因为去掉首字符后公共前缀长度减1若 s[i] s[j]则 lcp[i][j] lcp[i1][j1] 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 - iif 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[i1][j1] lcp[i][j] - 1if 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 [‘’] * nc ord(‘a’) # 当前可用的最小字符for i in range(n):if s[i]: # 已被前面的位置标记过continueif 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 1else:dp[i][j] 0for 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[i1][j1]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 矩阵与输入比对——这一步捕获该不等但 lcp0的反例例如 lcp[0][1]0 但构造出 s[0]s[1]‘a’复杂度时间O(n²) — 三次遍历 n×n 矩阵空间O(n²) — 存储验证用的 dp 矩阵
