Python DP Solution with Annotations
I just realized you can use DP to solve this problem, which is sort of strange that no one has mentioned it.\n\nThe code is not polished, so feel free to optimi
I just realized you can use DP to solve this problem, which is sort of strange that no one has mentioned it.\n\nThe code is not polished, so feel free to optimize it.\n\n```\nclass Solution:\n    def longestWord(self, words: List[str]) -> str:\n        \'\'\'\n        Initialize the dp table, where key is every word in the dictionary\n        and the value is a boolean value indciating whether this word\n        can be reached step by step\n        \'\'\'\n        table = {w : None for w in words}\n        \n        def dp(w):\n            \'\'\'\n            a recursive function that fills in the dp table\n            \'\'\'\n            nonlocal table\n            if len(w) == 0:\n                return True\n            elif w not in table:\n                return False\n            elif table[w] != None:\n                return table[w]\n            else:\n                return dp(w[:-1])\n        \n        cur_max, res = 0, \'\'\n        for word in words:\n            table[word] = dp(word)\n            if table[word]:\n                if len(word) > cur_max:\n                    cur_max = len(word)\n                    res = word\n                elif len(word) == cur_max and word < res:\n                    # if they have the same length and \n                    # this word is lexicographically smaller, replace the current res\n                    res = word\n        \n        return res\n```
['Dynamic Programming', 'Python3']