Hard

题目描述

我们定义由 n 个小写英文字母组成的字符串 word 的 lcp 矩阵为 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 中对应字母之前。例如，“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 <= 1000
  • 0 <= lcp[i][j] <= n

提示：

  • 使用 LCP 数组确定哪些元素组必须相等
  • 将最小的字母匹配到包含最小未分配索引的组
  • 构建结果字符串的 LCP 矩阵，然后检查它是否等于目标 LCP

解题思路

这道题需要根据最长公共前缀（LCP）矩阵来重建字符串。解题思路分为三个步骤：

步骤1：理解约束条件

  • 如果 lcp[i][j] > 0，那么 word[i] == word[j]（同一位置字符相等）
  • 如果 lcp[i][j] == 0，那么 word[i] != word[j]（同一位置字符不等）
  • 对角线元素 lcp[i][i] 应该等于 n-i（从位置i到末尾的长度）

步骤2：构造字符串 使用并查集思想，将必须相等的位置分组：

  • 遍历LCP矩阵，如果 lcp[i][j] > 0，则位置i和j必须使用相同字符
  • 为了得到字典序最小的结果，按索引顺序为每个组分配字母（‘a’, ‘b’, ‘c’…）

步骤3：验证结果 构造完字符串后，重新计算LCP矩阵并与给定矩阵比较：

  • 计算每对后缀的最长公共前缀长度
  • 如果计算结果与给定LCP矩阵不匹配，返回空字符串

这种方法确保了构造出的字符串既满足LCP约束，又是字典序最小的。

代码实现

class Solution {
public:
    string findTheString(vector<vector<int>>& lcp) {
        int n = lcp.size();
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        // Union positions that must have same character
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (lcp[i][j] > 0) {
                    int pi = find(i), pj = find(j);
                    if (pi != pj) {
                        parent[max(pi, pj)] = min(pi, pj);
                    }
                }
            }
        }
        
        // Assign characters
        string result(n, 'z');
        char ch = 'a';
        for (int i = 0; i < n; i++) {
            if (find(i) == i) {
                if (ch > 'z') return "";
                result[i] = ch++;
            }
        }
        
        for (int i = 0; i < n; i++) {
            result[i] = result[find(i)];
        }
        
        // Verify
        vector<vector<int>> computed(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int k = 0;
                while (i + k < n && j + k < n && result[i + k] == result[j + k]) {
                    k++;
                }
                computed[i][j] = k;
            }
        }
        
        return computed == lcp ? result : "";
    }
};

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # Union positions that must have same character
        for i in range(n):
            for j in range(n):
                if lcp[i][j] > 0:
                    pi, pj = find(i), find(j)
                    if pi != pj:
                        parent[max(pi, pj)] = min(pi, pj)
        
        # Assign characters
        result = ['z'] * n
        ch = ord('a')
        for i in range(n):
            if find(i) == i:
                if ch > ord('z'):
                    return ""
                result[i] = chr(ch)
                ch += 1
        
        for i in range(n):
            result[i] = result[find(i)]
        
        # Verify
        computed = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                k = 0
                while i + k < n and j + k < n and result[i + k] == result[j + k]:
                    k += 1
                computed[i][j] = k
        
        return ''.join(result) if computed == lcp else ""

public class Solution {
    public string FindTheString(int[][] lcp) {
        int n = lcp.Length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int Find(int x) {
            return parent[x] == x ? x : parent[x] = Find(parent[x]);
        }
        
        // Union positions that must have same character
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (lcp[i][j] > 0) {
                    int pi = Find(i), pj = Find(j);
                    if (pi != pj) {
                        parent[Math.Max(pi, pj)] = Math.Min(pi, pj);
                    }
                }
            }
        }
        
        // Assign characters
        char[] result = new char[n];
        char ch = 'a';
        for (int i = 0; i < n; i++) {
            if (Find(i) == i) {
                if (ch > 'z') return "";
                result[i] = ch++;
            }
        }
        
        for (int i = 0; i < n; i++) {
            result[i] = result[Find(i)];
        }
        
        // Verify
        int[][] computed = new int[n][];
        for (int i = 0; i < n; i++) {
            computed[i] = new int[n];
            for (int j = 0; j < n; j++) {
                int k = 0;
                while (i + k < n && j + k < n && result[i + k] == result[j + k]) {
                    k++;
                }
                computed[i][j] = k;
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (computed[i][j] != lcp[i][j]) return "";
            }
        }
        
        return new string(result);
    }
}

var findTheString = function(lcp) {
    const n = lcp.length;
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        return parent[x]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)构建并查集O(n²α(n))，验证LCP矩阵O(n³)
空间复杂度O(n²)存储并查集数组和验证矩阵