CPP | DFS and DP
Code

# Code
```cpp []
class Solution {
public:
    bool dfs(int i,char c, string &s, vector<vector<int>>&g)
    {
        s[i]=c;
        for(auto &j:g[i])
        {
            if(s[j]=='0' && !dfs(j,c,s,g))
               return false;
            if(s[j]!=c)
                return false;
        }
        return true;
    }
    string validate(string &s, vector<vector<int>>& lcp)
    {
        int n=s.size();
        vector<vector<int>>tmp(n,vector<int>(n,0));
        for(int i=n-1;i>=0;i--)
        {
            for(int k=0;k<=i;k++)
            {
                if(i==n-1)
                    tmp[i][k]=tmp[k][i]=(s[i]==s[k]);
                else
                {
                    if(s[i]==s[k])
                        tmp[i][k]=tmp[k][i]=1+tmp[i+1][k+1];
                } 

                if(lcp[i][k]!=tmp[i][k] || lcp[k][i]!=tmp[k][i])
                    return "";
            }
        }
        return s;
    }
    string findTheString(vector<vector<int>>& lcp) 
    {
        int n=lcp.size();
        vector<vector<int>>g(n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if((i+1<n && j+1<n && lcp[i][j]==lcp[i+1][j+1]+1) || (lcp[i][j]==1))
                {
                    g[i].push_back(j);
                    g[j].push_back(i);
                } 
            }
        }
        string s(n,'0');
        char c='a';
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')
            {
                if((c>'z') || !dfs(i,c,s,g))
                    return "";
                c++;   
            }  
        }
        return validate(s,lcp);
    }
};
```
['C++']