Check matrix property and then greedy decode
Intuition\n Describe your first thoughts on how to solve this problem. \nCheck properties of lcp matrix and then greedy decode the string.\n\n# Complexity\n- Ti
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCheck properties of lcp matrix and then greedy decode the string.\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size();\n        // Check matrix structure\n        // lcp[i][j] = lcp[j][i]\n        // lcp[i][i] = n - i\n        // lcp[i][j] > 0: lcp[i+1][j+1] =  lcp[i][j] - 1\n        // lcp[i][j] < n - i, lcp[i][j] < n - j\n        for (int i = 0; i < n; i++) {\n            if (lcp[i][i] != n - i) return "";\n            for (int j = 0; j < n; j++) {\n                if (lcp[i][j] != lcp[j][i]) return "";\n                if (lcp[i][j] > min(n - i, n - j)) return ""; \n                if (i + 1 < n && j + 1 < n && lcp[i][j] > 0) {\n                    if (lcp[i+1][j+1] + 1 != lcp[i][j]) return "";\n                }\n            }\n        }\n\n        vector<int> result(n, -1);\n        vector<vector<int>> isOK(n, vector<int>(26, 1));\n        for (int i = 0; i < n; i++) {\n            if (result[i] == -1) {\n                for (int j = 0; j < 26; j++) {\n                    if (isOK[i][j]) {\n                        result[i] = j;\n                        break;\n                    }\n                }\n                if (result[i] == -1) return "";\n            }\n            // Check and populate\n            for (int j = i+1; j < n; j++) {\n                if (lcp[i][j] == 0) {\n                    // conflict with existing letter\n                    if (result[j] >= 0 && result[j] == result[i]) return "";\n                    isOK[j][result[i]] = false;\n                } else {\n                    // conflict with existing letter\n                    if (result[j] >= 0 && result[j] != result[i]) return "";\n                    // conflict with can not fill\n                    if (result[j] == -1 && !isOK[j][result[i]]) return "";\n                    result[j] = result[i];\n                }\n            }\n        }\n        string s;\n        for (int c: result) s += char(c+\'a\');\n        return s;\n    }\n};\n```
['C++']