T2573.找出对应 LCP 矩阵的字符串

greedy, dp, string, matrix, https://leetcode.cn/problems/find-the-string-with-lcp/

对任一由 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 <= 1000
0 <= lcp[i][j] <= n

要构造满足 LCP（最长公共前缀）矩阵的字典序最小字符串，我们可以通过贪心策略来构建，然后通过动态规划进行有效性验证。

解题思路

贪心构造：
- 为了得到字典序最小的字符串，我们应该尽可能使用靠前的字母（'a' 到 'z'）。
- 遍历 $i$ 从 $0$ 到 $n - 1$ ：
  - 如果 res[i] 已经填入了字符，说明它之前被某个更小的索引 $j$ 通过 $l c p [j] [i] > 0$ 的关系确定了。
  - 如果 res[i] 还没有字符，我们需要分配一个新的最小可用字母。如果没有字母可用了（超过 26 个字母），则返回空字符串。
  - 根据 LCP 的定义，如果 $l c p [i] [j] > 0$ ，那么索引 $i$ 和 $j$ 处的字符必须相等（word[i] == word[j]）。因此，我们将 res[i] 的字符分配给所有满足 $l c p [i] [j] > 0$ 的位置 $j$ 。
有效性验证：
- 贪心构造出的字符串只是一个“候选者”。我们需要验证这个字符串生成的 LCP 矩阵是否与输入矩阵完全一致。
- 我们定义 $d p [i] [j]$ 为后缀 word[i:] 和 word[j:] 的最长公共前缀长度。
- 转移方程：
  - 若 word[i] == word[j]： $d p [i] [j] = d p [i + 1] [j + 1] + 1$ （若超出边界则为 1）。
  - 若 word[i] != word[j]： $d p [i] [j] = 0$ 。
- 最后，检查每一项 $d p [i] [j]$ 是否等于输入的 $l c p [i] [j]$ 。如果不等，说明输入的矩阵不合法，返回空字符串。
代码实现

python

from typing import List

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        res = [""] * n
        curr_char_idx = 0
        
        # 1. 贪心构造候选字符串
        for i in range(n):
            if res[i] != "":
                continue
            
            # 只有 26 个小写英文字母可用
            if curr_char_idx >= 26:
                return ""
            
            char = chr(ord('a') + curr_char_idx)
            curr_char_idx += 1
            
            # 如果 lcp[i][j] > 0，则 word[i] 必须等于 word[j]
            for j in range(i, n):
                if lcp[i][j] > 0:
                    res[j] = char
        
        # 如果还有空缺（通常不会发生，除非矩阵定义极度异常），直接非法
        if "" in res:
            return ""
            
        word = "".join(res)
        
        # 2. 验证构造出的字符串是否真的产生给定的 lcp 矩阵
        # 我们使用动态规划 O(n^2) 计算该字符串的 LCP
        # dp[i][j] 表示 word[i:] 和 word[j:] 的 LCP 长度
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if word[i] == word[j]:
                    dp[i][j] = dp[i + 1][j + 1] + 1
                else:
                    dp[i][j] = 0
                
                # 一旦发现计算值与输入不符，说明矩阵不成立
                if dp[i][j] != lcp[i][j]:
                    return ""
                    
        return word

复杂度分析

时间复杂度： $O (n^{2})$ 。构造字符串的过程是 $O (n^{2})$ ，验证 LCP 矩阵的动态规划过程也是 $O (n^{2})$ 。其中 $n \leq 1000$ ， $n^{2}$ 约为 $10^{6}$ ，在 Python 的执行时限内。
空间复杂度： $O (n^{2})$ 。我们需要存储一个 $n \times n$ 的 DP 验证矩阵（约 4-8 MB）。

为什么这个方法能保证字典序最小？

我们的贪心策略是：从左到右扫描字符串。每当遇到一个尚未归类的位置 $i$ 时，我们赋予它能用的最小字符（从 'a' 开始）。因为 $i$ 是当前最小的未确定索引，且赋予的是最小可能的字符，这样生成的字符串在所有可能生成的合法字符串中，字典序一定是最小的。

T2573.找出对应 LCP 矩阵的字符串 ​

T2573.找出对应 LCP 矩阵的字符串