LeetCode 题解工作台
找出对应 LCP 矩阵的字符串
对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足： lcp[i][j] 等于子字符串 word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。 给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字…
6
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
由于构造的字符串要求字典序最小，因此我们可以从字符 `'a'` 开始，填充到字符串 中。 如果当前位置 还未填充字符，那么我们可以将字符 `'a'` 填充到 位置，然后枚举所有 $j \gt i$ 的位置，如果 $lcp[i][j] \gt 0$，那么位置 也应该填充字符 `'a'`。然后我们将字符 `'a'` 的 ASCII 码加一，继续填充剩余未填充的位置。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足：
lcp[i][j]等于子字符串word[i,...,n-1]和word[j,...,n-1]之间的最长公共前缀的长度。
给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串，则返回空字符串。
对于长度相同的两个字符串 a 和 b ，如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的顺序先于 b 中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca" ，因为二者不同的第一位置是第三个字母，而 'b' 先于 'c' 出现。
示例 1：
输入：lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]] 输出："abab" 解释：lcp 对应由两个交替字母组成的任意 4 字母字符串，字典序最小的是 "abab" 。
示例 2：
输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]] 输出："aaaa" 解释：lcp 对应只有一个不同字母的任意 4 字母字符串，字典序最小的是 "aaaa" 。
示例 3：
输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]] 输出："" 解释：lcp[3][3] 无法等于 3 ，因为 word[3,...,3] 仅由单个字母组成；因此，不存在答案。
提示：
1 <= n ==lcp.length ==lcp[i].length<= 10000 <= lcp[i][j] <= n
解题思路
方法一：贪心 + 构造
由于构造的字符串要求字典序最小，因此我们可以从字符 'a' 开始，填充到字符串 中。
如果当前位置 还未填充字符，那么我们可以将字符 'a' 填充到 位置，然后枚举所有 的位置，如果 ，那么位置 也应该填充字符 'a'。然后我们将字符 'a' 的 ASCII 码加一，继续填充剩余未填充的位置。
填充结束后，如果字符串中存在未填充的位置，说明无法构造出对应的字符串，返回空字符串。
接下来，我们可以从大到小枚举字符串中的每个位置 和 ，然后判断 和 是否相等：
- 如果 ，此时我们需要判断 和 是否为字符串的最后一个位置，如果是，那么 应该等于 ，否则 应该等于 。如果不满足上述条件，说明无法构造出对应的字符串，返回空字符串。如果 和 不是字符串的最后一个位置，那么 应该等于 ，否则说明无法构造出对应的字符串，返回空字符串。
- 否则，如果 ，说明无法构造出对应的字符串，返回空字符串。
如果字符串中的每个位置都满足上述条件，那么我们就可以构造出对应的字符串，返回即可。
时间复杂度为 ，空间复杂度为 。其中 为字符串的长度。
class Solution:
def findTheString(self, lcp: List[List[int]]) -> str:
n = len(lcp)
s = [""] * n
i = 0
for c in ascii_lowercase:
while i < n and s[i]:
i += 1
if i == n:
break
for j in range(i, n):
if lcp[i][j]:
s[j] = c
if "" in s:
return ""
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if s[i] == s[j]:
if i == n - 1 or j == n - 1:
if lcp[i][j] != 1:
return ""
elif lcp[i][j] != lcp[i + 1][j + 1] + 1:
return ""
elif lcp[i][j]:
return ""
return "".join(s)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) due to checking all pairs in the LCP matrix and propagating equivalences. Space complexity is O(n) to store equivalence classes and the resulting string, though the LCP matrix itself requires O(n^2) storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate identifies matrix symmetry and self-prefix conditions.
- question_mark
Candidate uses dynamic programming to propagate equality constraints efficiently.
- question_mark
Candidate correctly detects impossible LCP configurations and returns empty string.
常见陷阱
外企场景- error
Ignoring symmetry and failing to check lcp[i][j] == lcp[j][i].
- error
Assigning letters before resolving all equivalence classes, which may violate LCP rules.
- error
Misinterpreting lexicographical ordering when multiple choices of letters exist.
进阶变体
外企场景- arrow_right_alt
Find the largest lexicographical string matching an LCP matrix.
- arrow_right_alt
Handle LCP matrices with wildcard entries represented by -1.
- arrow_right_alt
Extend the problem to uppercase letters or a custom alphabet.