[Python 3]Union Find
```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)       \n        \n        loc = list(range(n))\n        \n
```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        n = len(lcp)       \n        \n        loc = list(range(n))\n        \n        def find(x):\n            if loc[x] != x:\n                loc[x] = find(loc[x])\n            return loc[x]\n        \n        def union(x, y):\n            a, b = find(x), find(y)\n            if a < b:\n                loc[b] = a\n            else:\n                loc[a] = b        \n        \n        \n        for i in range(n):\n            for j in range(i+1):\n                # the tricky part is that the value of lcp doesn\'t matter here, as long as > 0, just union the index, will check the value later on\n                if lcp[i][j]: union(i, j) \n        \n        g = [find(i) for i in range(n)]\n        \n\n        # check if the built union-find group is valid\n        # based on @lee215\'s solution\n        # lcp[i][j] must equal lcp[i+1][j+1] + 1 if (i, j) shares common prefix\n        for i in range(n):\n            for j in range(n):\n                v = lcp[i+1][j+1] if i < n - 1 and j < n - 1 else 0\n                v = v + 1 if g[i] == g[j] else 0\n                if v != lcp[i][j]:\n                    return ""\n        \n        # collapse grop sequence number to most smallest character index \n        # for example if group number is [0, 2] then collapse to [0, 1]\n        grp = set(g)\n        if len(grp) > 26: return ""\n        grp = {x: i for i, x in enumerate(sorted(grp))}\n        \n        ans = []\n        for i, k in enumerate(g):\n            ans.append(chr(97+grp[k]))           \n        \n        \n        return "".join(ans)
['Union Find', 'Python', 'Python3']