Union Find
It passed, but my instinction tells me that there might be some corner cases that would fail this simple solution that does not even use the exact value of lcp[
It passed, but my instinction tells me that there might be some corner cases that would fail this simple solution that does not even use the exact value of lcp[i][j] in the first loop ... \n\n# Code\n```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)\n        p = [i for i in range(n)]\n        def find(x):\n            if x!=p[x]:\n                p[x] = find(p[x])\n            return p[x]\n        \n        for i in range(n-1,-1,-1):\n            for j in range(i,-1,-1):\n                if i == j and lcp[i][j]!=n-i:return ""\n                if i!=j:\n                    if lcp[i][j]!=lcp[j][i]: return ""\n                    if lcp[i][j]>0:\n                        pi,pj = sorted([find(i),find(j)])\n                        if pi!=pj:\n                            p[pj] = pi\n        ff = [find(i) for i in range(n)]\n        res = \'\'\n        dic = {}\n        unused = 0\n        for i in range(n):\n            if ff[i] in dic:\n                res += dic[ff[i]]\n            else:\n                if unused >= 26: return \'\'\n                dic[ff[i]] = chr(ord(\'a\')+unused)\n                unused += 1\n                res += dic[ff[i]]\n        for i in range(n):\n            for j in range(i+1,n):\n                a = lcp[i][j]\n                if res[i:i+a]!=res[j:j+a]:return \'\'\n                if i+a < n and j+a < n and res[i:i+a+1]==res[j:j+a+1]:return \'\'\n\n        return res\n                    \n\n        \n        \n\n        \n```
['Union Find', 'Python3']