Python (Union Find)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findTheString(self, lcp):\n        n = len(lcp)\n\n        dict1 = defaultdict(int)\n\n        def find(x):\n            if x not in dict1:\n                return x\n            else:\n                if x != dict1[x]:\n                    dict1[x] = find(dict1[x])\n                return dict1[x]\n\n        def union(x,y):\n            a,b = find(x),find(y)\n\n            if a > b:\n                dict1[a] = b\n            else:\n                dict1[b] = a\n\n        for i in range(n):\n            for j in range(i):\n                if lcp[i][j]: union(i,j)\n\n        ans = [find(i) for i in range(n)]\n\n        for i in range(n):\n            for j in range(n):\n                val = lcp[i+1][j+1] if i+1 < n and j+1 < n else 0\n                val = val + 1 if ans[i] == ans[j] else 0\n                if val != lcp[i][j]:\n                    return ""\n\n        group = set(ans)\n        if len(group) > 26: return ""\n        dict2 = {x:i for i,x in enumerate(sorted(group))}\n\n        res = []\n\n        for i,k in enumerate(ans):\n            res.append(chr(97+dict2[k]))\n\n        return "".join(res)\n\n\n\n\n\n\n\n\n        \n\n\n\n\n\n        \n\n        \n\n            \n\n        \n\n\n        \n```
['Python3']