C++/Rust Brute Force
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)$$ -->\nO( N * N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\n// Thanks https://leetcode.com/Rook_Lift/ for point out that \n//verification was actually O(N * N * N), instead of O(N & N).\n//It was improved to achieve O(N * N).\n// Rust solution was also included. \nclass Solution {\npublic:\n    string findTheString(vector<vector<int>>& lcp) {\n        int n = lcp.size();\n        vector<char> ret(n, \' \');\n        \n        char c = \'a\';\n        for (int i = 0; i < n; ++i) {\n            if (ret[i] != \' \') continue;\n                \n            if (c > \'z\') return "";\n            ret[i] = c;\n            c += 1;\n            \n            for (int k = i + 1; k < n; ++k) {\n                if (lcp[i][k] != 0) ret[k] = ret[i];\n            }\n        }\n        \n        for (int k = 0; k < n; ++k) {\n            for (int i = n - 1 - k; i >= 0; --i) {\n                int a = 0;\n                if (ret[i] == ret[i + k]) {\n                    a = 1;\n                    if (i + k + 1 < n) a += lcp[i + 1][i + k + 1]; \n                }\n                if (lcp[i][i + k] != a or lcp[i + k][i] != a) return "";\n            } \n        }\n        \n        string s;\n        for (auto &c: ret) s += c;\n        return s;\n    }\n};\n```\n~~~\n// Rust\nimpl Solution {\n    pub fn find_the_string(lcp: Vec<Vec<i32>>) -> String {\n        let n = lcp.len();\n        let mut data = vec![\' \'; n];\n\n        let mut c = \'a\';\n        for i in 0 .. n {\n            if data[i] != \' \' { continue }\n            if c > \'z\' { return String::new() }\n            \n            data[i] = c;\n            c = (c as u8 + 1) as char;\n\n            for k in i + 1 .. n {\n                if lcp[i][k] != 0 { data[k] = data[i]; }\n            } \n        }\n\n        for k in 0 .. n {\n            for i in (0 .. n - k).rev() {\n                let mut a = 0;\n                if data[i] == data[i + k] {\n                    a = 1;\n                    if i + k + 1 < n { a += lcp[i + 1][i + k + 1]; }\n                }\n                if lcp[i][i + k] != a || lcp[i + k][i] != a { return String::new() }\n            }\n        }\n\n        data.into_iter().collect()\n    }\n}\n~~~\n\n
['C++', 'Rust']