[Python 3] Build pattern & Validate lcp - O(N^2)
Complexity\n- Time complexity: $O(N^2)$\n\n- Space complexity: $O(N^2)$ (can be reduced to $O(N)$ if build and check new lcp at the same time)\n\n# Code\n\nclas
# Complexity\n- Time complexity: $O(N^2)$\n\n- Space complexity: $O(N^2)$ (can be reduced to $O(N)$ if build and check new lcp at the same time)\n\n# Code\n```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        # simple validation\n        n = len(lcp)\n        for i in range(n):\n            for j in range(i + 1, n):\n                if lcp[i][j] != lcp[j][i]:\n                    return \'\'\n                if lcp[i][j] > n - j:\n                    return \'\'\n        for i in range(n):\n            if lcp[i][i] != n - i:\n                return \'\'\n        \n        # build pattern \u2014 the only possible candidate for answer\n        pattern = [None for _ in range(n)]\n        next_el_ind = 0\n        for i in range(n):\n            if pattern[i] is not None:\n                continue\n            pattern[i] = next_el_ind\n            next_el_ind += 1\n            for j in range(i+1, n):\n                if lcp[i][j] > 0:\n                    if pattern[j] is not None and pattern[j] != pattern[i]:\n                        return \'\'\n                    pattern[j] = pattern[i]\n    \n        # check if lcp is valid - check that pattern\'s lcp == original lcp\n        pattern_lcp = [[0 for _ in range(n)] for _ in range(n)]\n        for i in range(n-1, -1, -1):\n            for j in range(n-1, -1, -1):\n                if pattern[i] == pattern[j]:\n                    if max(i, j) + 1 < n:\n                        pattern_lcp[i][j] = pattern_lcp[i+1][j+1] + 1\n                    else:\n                        pattern_lcp[i][j] = 1\n        for i in range(n):\n            for j in range(n):\n                if lcp[i][j] != pattern_lcp[i][j]:\n                    return \'\'\n    \n        # check that answer has no more than 26 distinct elements\n        if max(pattern) > ord(\'z\') - ord(\'a\'):\n            return \'\'\n\n        return  \'\'.join(chr(ord(\'a\') + ind) for ind in pattern)\n```
['Python3']