DeepSeek LeetCode 2573. 找出对应 LCP 矩阵的字符串 Java实现

这道题要求根据 LCP (最长公共前缀) 矩阵还原出一个由小写字母组成的字符串。

解题思路

1. 理解 LCP 矩阵性质：
· LCP[i][j] 表示字符串第 i 个字符和第 j 个字符开头后缀的最长公共前缀长度
· 对角线一定是字符串长度
· 矩阵对称
· 若 LCP[i][j] > 0，则 s[i] == s[j]
2. 构造策略：
· 贪心分配字母：从第一个字符开始，如果某个位置未赋值，尽可能赋最小的可行字母
· 验证构造的字符串是否满足 LCP 矩阵

Java 实现

```java
class Solution {
public String findTheString(int[][] LCP) {
int n = LCP.length;
char[] s = new char[n];

// 贪心构造字符串
char currentChar = 'a';
for (int i = 0; i < n; i++) {
if (s[i] == 0) { // 未赋值
if (currentChar > 'z') {
return ""; // 需要超过26个字母，不可能
}
// 给所有与 i 有相同字符的位置赋值
for (int j = i; j < n; j++) {
if (LCP[i][j] > 0) {
s[j] = currentChar;
}
}
currentChar++;
}
}

// 验证构造的字符串是否满足 LCP 矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int expected = LCP[i][j];
int actual = computeLCP(s, i, j, n);
if (expected != actual) {
return "";
}
}
}

return new String(s);
}

private int computeLCP(char[] s, int i, int j, int n) {
if (i == j) return n - i;
if (s[i] != s[j]) return 0;

int len = 0;
while (i + len < n && j + len < n && s[i + len] == s[j + len]) {
len++;
}
return len;
}
}
```

优化验证方法

上面的验证方法 O(n³)，可以优化到 O(n²)：

```java
class Solution {
public String findTheString(int[][] LCP) {
int n = LCP.length;
char[] s = new char[n];

// 第一步：贪心构造
char currentChar = 'a';
for (int i = 0; i < n; i++) {
if (s[i] == 0) {
if (currentChar > 'z') return "";
for (int j = i; j < n; j++) {
if (LCP[i][j] > 0) {
s[j] = currentChar;
}
}
currentChar++;
}
}

// 第二步：O(n²) 验证
// 验证 LCP[i][j] 和字符相等关系的一致性
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
if (LCP[i][j] != n - i) return "";
} else {
if (LCP[i][j] != LCP[j][i]) return "";
if (LCP[i][j] > n - Math.max(i, j)) return "";

if (s[i] != s[j]) {
if (LCP[i][j] != 0) return "";
} else {
if (i + 1 < n && j + 1 < n) {
if (LCP[i][j] != 1 + LCP[i + 1][j + 1]) return "";
} else {
if (LCP[i][j] != 1) return "";
}
}
}
}
}

return new String(s);
}
}
```

核心要点

1. 正确性：利用 LCP 矩阵的性质，如果 LCP[i][j] > 0，则 s[i] == s[j]，可以用这个条件将字符分组
2. 贪心赋值：按顺序给每个未赋值的组分配最小的可用字母
3. 验证：必须验证构造的字符串是否完全满足 LCP 矩阵，因为 LCP[i][j] > 0 只是必要条件，不是充分条件
4. 时间复杂度：构造 O(n²)，验证 O(n²)，总体 O(n²)