Python | Build Word and then Check by Z-function, O(N*N) | Explanation
Because lcp[i][j] is equal to the length of the longest common prefix, so if lcp[i][j] > 0, then word[i] must equals to word[j].\nSo, we iterate from lcp[0] to 
Because `lcp[i][j] is equal to the length of the longest common prefix`, so if `lcp[i][j] > 0`, then `word[i]` must equals to `word[j]`.\nSo, we iterate from `lcp[0]` to `lcp[i]` to assign `word[i]` first if not assigned, and then iterate `lcp[i][j]` to assign `word[j] = word[i]` where `lcp[i][j]>0`.\nIt\'s worth noting that we assign character from `a` to `z`, so `word` is guaranteed to be  the alphabetically smallest string.\nAfter assigning `word`, we start to check `lcp`.\nFor every `i` and `j` where `j>i`, we are going to check:\n* lcp[i][j] == lcp[j][i]\n* lcp[i][i] == len(lcp) - i\n* lcp[i][j] == z~i~[j-i], where z~i~ is the result of `z_function(word[i:])`\n\nZ-function is used to calculate the length of the longest common prefix where the `i`-th element of z-function(`s`) is the length of the longest common prefix of `s` and `s[i:]`.\nThat is, the `k`-th index of z_function(`word[i:]`) is the length of the longest common prefix of `word[i:]` and `word[i+k:]`, which is `lcp[i][i+k]`.\nZ-function only cost O(N+M) Time complexity and we call it N times in the code, resulting in a total of O(N\\*N) Time Complexity.\n\nIf passed, then `word` is the answer.\n\n```python []\ndef z_function(s):\n    n = len(s)\n    z = [0] * n\n    l, r = 0, 0\n    for i in range(1, n):\n        if i <= r and z[i - l] < r - i + 1:\n            z[i] = z[i - l]\n        else:\n            z[i] = max(0, r - i + 1)\n            while i + z[i] < n and s[z[i]] == s[i + z[i]]:\n                z[i] += 1\n        if i + z[i] - 1 > r:\n            l = i\n            r = i + z[i] - 1\n    return z\n\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        ans = [\'\'] * len(lcp)\n        nowuse = \'a\'\n        for i, lis in enumerate(lcp):\n            if ans[i] == \'\':\n                if nowuse > \'z\':\n                    return \'\'\n                ans[i] = nowuse\n                nowuse = chr(ord(nowuse) + 1)\n            for j, n in enumerate(lis):\n                if n != 0:\n                    if ans[j] == \'\':\n                        ans[j] = ans[i]\n        \n        for i in range(len(lcp)):\n            for j in range(len(lcp)):\n                # check symmetry\n                if lcp[i][j] != lcp[j][i]:\n                    return ""\n            # check diagonal\n            if lcp[i][i] != len(lcp) - i:\n                return ""\n            # get z-function result given ans[i:]\n            z = z_function(ans[i:])\n            # for each i, because it\'s symmetry, we only check lcp[i][j] where j > i\n            for j in range(i+1, len(lcp)):\n                if lcp[i][j] != z[j-i]:\n                    return ""\n        return \'\'.join(ans)\n```
['Python3']