找出对应 LCP 矩阵的字符串

标签: 贪心 并查集 数组 字符串 动态规划 矩阵

难度: Hard

对任一由 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

Submission

运行时间: 119 ms

内存: 71.4 MB

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        if lcp[-1][-1] != 1:
            return ""
        n = len(lcp)
        idx, r = 0, [''] * n
        for c in ascii_lowercase:
            while idx < n and r[idx]:
                idx += 1
            if idx == n:
                break
            for i in range(idx, n):
                if lcp[idx][i]:
                    r[i] = c
        if '' in r:
            return ""
        for i in range(n - 1):
            now = lcp[-1][i]
            if now != 1 and r[i] == r[-1] or now != 0 and r[i] != r[-1] or now != lcp[i][-1]:
                return ""
        for i in range(n - 2, -1, -1):
            for j in range(i, -1, -1):
                if r[i] == r[j] and lcp[i][j] != lcp[i+1][j+1] + 1 or r[i] != r[j] and lcp[i][j] != 0:
                    return ""
        return "".join(r)

Explain

该题解尝试通过逐步构建字符串 `word` 来满足给定的 LCP 矩阵的约束。首先检查矩阵的最后一个元素，它应表示单个字符的最长公共前缀，因此必须为 1。接着，使用一个循环遍历所有可能的字符（从 'a' 到 'z'），并尝试将这些字符按需分配到结果字符串中的相应位置。对每个字符，从左至右检查是否可以放置该字符，确保满足 LCP 值的要求。通过逐个添加字符，构建整个字符串。最后，检查构建的字符串是否完全符合 LCP 矩阵的要求，包括字符间的比较和最长公共前缀的检验。如果在任何阶段发现矩阵的要求无法被满足，就返回空字符串。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        if lcp[-1][-1] != 1:
            return ""  # 检查最后一个字符的自相似性
        n = len(lcp)
        idx, r = 0, [''] * n  # 初始化索引和结果字符串数组
        for c in ascii_lowercase:  # 遍历所有可能的字符
            while idx < n and r[idx]:
                idx += 1  # 找到下一个空的位置
            if idx == n:
                break  # 如果已填满，停止
            for i in range(idx, n):
                if lcp[idx][i]:
                    r[i] = c  # 填充字符
        if '' in r:
            return ""  # 检查是否有未填充的位置
        for i in range(n - 1):
            now = lcp[-1][i]
            if now != 1 and r[i] == r[-1] or now != 0 and r[i] != r[-1] or now != lcp[i][-1]:
                return ""  # 验证最后一行的约束
        for i in range(n - 2, -1, -1):
            for j in range(i, -1, -1):
                if r[i] == r[j] and lcp[i][j] != lcp[i+1][j+1] + 1 or r[i] != r[j] and lcp[i][j] != 0:
                    return ""  # 验证所有 LCP 约束
        return \"\".join(r)  # 返回结果字符串

Explore

在构建字符串时，检查 lcp[-1][-1] 必须为 1 是因为这个值代表字符串中最后一个字符和它自己的最长公共前缀长度，理应为 1。这确保了矩阵的一致性和算法的有效性。如果 lcp[-1][-1] 不是 1，则意味着矩阵自身可能存在错误或不符合最长公共前缀的定义，因此算法无法继续构建有效的字符串。

算法通过确保从左到右填充字符时，每个字符位置都满足从该位置开始到字符串末尾的所有 LCP 值。这是通过设置循环，一旦字符被分配到某个位置，接下来的所有位置到字符串末尾的 LCP 值都将被检查和满足。如果在任何位置发现不满足 LCP 值的情况，这个字符的分配就是错误的，因此算法会回溯或尝试另一个字符。

具体情况包括：1) 如果在填充字符过程中发现任何位置的字符无法满足与其它位置的 LCP 值要求；2) 如果在构建完字符串后，最后的验证步骤中发现任何一对字符的实际 LCP 与矩阵中的 LCP 值不匹配；3) 如果在尝试填充所有字符后还有位置为空，意味着没有合适的字符可以满足所有 LCP 条件。这些情况都会导致算法无法构建一个符合所有 LCP 条件的字符串，因此返回空字符串。

最终验证步骤中，算法通过遍历字符串中的每一对字符，并比较它们的实际最长公共前缀长度与 LCP 矩阵中对应的值。验证规则如下：如果两个字符相同，那么它们的 LCP 应该是它们之间距离的累加；如果不同，则 LCP 应该为 0。此外，还会验证字符数组的最后一行是否符合之前填充的字符和它们对应的 LCP 值。如果任何一对字符的验证失败，算法将返回空字符串。