https://leetcode.com/problems/word-break/\n\n<details> \n  <summary>My solution</summary>\n\nI wrote this O(n^2) dp solution in the interview as the following (bug free). The interviewer was quite unhappy. I got rejected for this. He mentioned that he expected a solution better than O(n^2) while I did not know how. I searched online and couldn\'t find one so far.\n\n```\nclass Solution:\n    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n        wordDict = set(wordDict)\n        n = len(s)\n        dp = [0] * (n + 1)\n        dp[0] = 1\n        for i, _ in enumerate(s):\n            for j in range(i, -1, -1):\n                if s[j: i + 1] in wordDict and dp[j] == 1:\n                    dp[i+1] = 1\n                    break\n        return dp[n]\n```\n</details>\n\nResult: Rejected.

https://leetcode.com/problems/word-break/\n\n \n  My solution\n\nI wrote this O(n^2) dp solution in the interview as the following (bug free). The interviewer w