这道题要求根据 LCP (最长公共前缀) 矩阵还原出一个由小写字母组成的字符串。解题思路1. 理解 LCP 矩阵性质· LCP[i][j] 表示字符串第 i 个字符和第 j 个字符开头后缀的最长公共前缀长度· 对角线一定是字符串长度· 矩阵对称· 若 LCP[i][j] 0则 s[i] s[j]2. 构造策略· 贪心分配字母从第一个字符开始如果某个位置未赋值尽可能赋最小的可行字母· 验证构造的字符串是否满足 LCP 矩阵Java 实现javaclass 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²)javaclass 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²)
