[Python] Construct and Check through every case I failed :(
Intuition\n\nif lcp[i][j] > 0, it means words[i:i+lcp[i][j]] == words[j:j+lcp[i][j]]\nthus, we can know that words[i] = words[j] if lcp[i][j] > 0\n\nsince we wa
# Intuition\n\nif lcp[i][j] > 0, it means words[i:i+lcp[i][j]] == words[j:j+lcp[i][j]]\nthus, we can know that words[i] = words[j] if lcp[i][j] > 0\n\nsince we want alphabetically smallest string, we can iterate i from `0 to n-1` and assign from `a to z` one by one **if lcp[i][j] > 0**\n\nif we already assigned character before, we skip it because it\'s already possible alphabetically smallest character\n\nafter we construct possible solution to alphabetically smallest string, we still need to check if lcp matrix is valid or not.\n\nthe conditions are the same as we construct string:\n\n1. if `i+lcp[i][j] > n` or `j+lcp[i][j]`, it\'s **invalid**. (see example 3)\n2. if **words[i] == words[j]**:\n    - lcp[i][j] should be greater than 0\n    - lcp[i][j] should equals lcp[i+1][j+1]+1\n3. if **words[i] != words[j]**:\n    - it\'s opposite from second condition\n    - lcp[i][j] should be 0\n    - lcp[i][j] should **NOT** equal lcp[i+1][j+1]+1\n4. length of final words we constructed should equal `n`\n\n    ```py\n    ans = "".join(words)\n    if len(ans) != n: return ""\n    ```\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def findTheString(self, lcp: List[List[int]]) -> str:\n        # lcp[i][j]: length of common prefix word[i:] and word[j]\n        n = len(lcp)\n        words = [""]*n\n        shift = 0\n        for i in range(n):\n            if words[i]: continue\n            for j in range(n):\n                if words[j]: continue\n                # words[i:i+lcp[i][j]] == words[j:j+lcp[i][j]]\n                # -> words[i] == words[j]\n                if lcp[i][j] > 0:\n                    words[i] = chr(ord(\'a\')+shift) if shift < 26 else ""\n                    words[j] = words[i]\n            shift += 1\n\n        for i in range(n):\n            for j in range(n):\n                # example 3\n                if i+lcp[i][j] > n or j+lcp[i][j] > n: return ""\n                \n                if words[i] == words[j]:\n                    # case: [[2,1],[0,1]]\n                    if lcp[i][j] == 0: return ""\n                    # case: [[4,1,1,1],[1,1,1,1],[1,1,1,1],[1,1,1,1]]\n                    if i<n-1 and j<n-1 and lcp[i][j] != lcp[i+1][j+1]+1:\n                        return ""\n                else:\n                    if lcp[i][j] != 0: return ""\n                    if i<n-1 and j<n-1 and lcp[i][j] == lcp[i+1][j+1]+1:\n                        return ""\n        \n        # final case\n        ans = "".join(words)\n        if len(ans) != n: return ""\n        return ans\n```
['Python3']