C++ Solution Union Find
Code\n\nclass Solution {\npublic:\n    vector<int>fa;\n    int findFather(int x)\n    {\n        if(fa[x]==x)return x;\n        return fa[x]=findFather(fa[x]);\
# Code\n```\nclass Solution {\npublic:\n    vector<int>fa;\n    int findFather(int x)\n    {\n        if(fa[x]==x)return x;\n        return fa[x]=findFather(fa[x]);\n    }\n    void Union(int x,int y)\n    {\n        x=fa[x];\n        y=fa[y];\n        fa[y]=x;\n        return;\n    }\n    string findTheString(vector<vector<int>>& lcp)\n    {\n        int n=lcp.size();\n        fa.resize(n);\n        for(int i=0;i<n;i++)fa[i]=i;\n        for(int i=0;i<n;i++)\n            for(int j=0;j<n;j++)\n            {\n                if(lcp[i][j]==0)continue;\n                if(findFather(i)!=findFather(j))Union(i,j);\n                if(i==j&&(lcp[i][j]!=n-i))return "";\n            }\n        set<int>Set;\n        for(int i=0;i<n;i++)Set.insert(findFather(i));\n        if(Set.size()>26)return "";\n        map<int,char>Map;\n        char c=\'a\';\n        string res="";\n        for(int i=0;i<n;i++)\n        {\n            if(Map.count(fa[i])==false)\n            {\n                Map[fa[i]]=c;\n                c++;\n            }\n            res.push_back(Map[fa[i]]);\n        }\n        vector<vector<int>>f(n,vector<int>(n,0));\n        for(int i=n-1;i>=0;i--)\n            for(int j=n-1;j>=0;j--)\n            {\n                if(res[i]!=res[j])f[i][j]=0;\n                else if(i+1<n&&j+1<n)f[i][j]=f[i+1][j+1]+1;\n                else f[i][j]=1;\n            }\n        for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(f[i][j]!=lcp[i][j])return "";\n        return res;\n    }\n};\n```
['Union Find', 'C++']