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

我最初想到的办法非常复杂，其实是去根据已有的条件尝试构建连通图

构建的时候会验证对称性和grid[i][j]>1的情况
最后验证的时候会验证grid[i][j]=0的情况

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        # quick check and build graph
        grid = [[] * n for _ in range(n)]
        for i in range(n):
            if lcp[i][i] != (n - i):
                return ''
            for j in range(i + 1, n):
                if lcp[i][j] != lcp[j][i]:
                    return ''
                d = lcp[i][j]
                if d > (n - max(i, j)):
                    return ''
                if d > 0:
                    if (j + 1) < n and lcp[i + 1][j + 1] != (d - 1):
                        return ''
                    grid[i].append(j)
                    grid[j].append(i)

        # dfs and build connected graph.
        ts = [0] * n

        def dfs(x, now):
            if ts[x] != 0:
                return ts[x] == now
            ts[x] = now
            for y in grid[x]:
                if not dfs(y, now):
                    return False
            return True

        now = 1
        for i in range(n):
            if ts[i]: continue
            # too much connected graphs.
            if now > 26: return ''
            if not dfs(i, now):
                return ''
            now += 1

        ans = [''] * n
        for i in range(n):
            ans[i] = chr(ord('a') + ts[i] - 1)
        ans = ''.join(ans)

        # double check because we only looks for positive requirements.
        # we need to take care of negative requirements.
        for i in range(n):
            for j in range(i + 1, n):
                if lcp[i][j] == 0 and ans[i] == ans[j]:
                    return ''

        return ans

题解中的解法思路也差不多，但是构建方式不同，所以代码异常地简单：

首先给 a[i] 分配一个目前还没有使用的字符
然后根据 grid[i][j] > 0 条件，将字符分配给 a[j]
如果字符不够的话，那么直接返回
但是根据这个条件构建的图，仅仅是满足 grid[i][j] > 0的条件，并没有满足
- 长度>1时候的条件
- 以及grid[i][j] = 0的条件
所有需要最后一步进行验证，包括矩阵是否对称。

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        ans = [''] * n

        # construct loosely answer.
        import string
        i = 0
        for c in string.ascii_lowercase:
            while i < n and ans[i] != '': i += 1
            if i == n: break
            for j in range(i, n):
                if lcp[i][j]: ans[j] = c
        if '' in ans: return ''

        for i in reversed(range(n)):
            for j in reversed(range(i, n)):
                if lcp[i][j] != lcp[j][i]: return ''
                value = 0
                if ans[i] == ans[j]:
                    value = lcp[i + 1][j + 1] if (j + 1) < n else 0
                    value += 1
                if lcp[i][j] != value:
                    return ''

        return ''.join(ans)