WORD BREAK II (Leetcode) - Code & Whiteboard скачать в хорошем качестве

WORD BREAK II (Leetcode) - Code & Whiteboard

An intuitive solution to a classic, albeit difficult, problem -- Leetcode 140: Word Break II. (Complexity analysis below). Let me know if you have any questions down below! Time Complexity: O(n * 2^n), where n is the number of characters. In a worst case scenario Space Complexity: O(n * 2^n) There seems to be some disagreement online about the complexity of this problem; consider the following example to see the worst case scenario: s = aaaaaa wordDict = [a, aa, aaa, aaaa, aaaaa, aaaaaa] Our memo would look something like: { "a": ["a"] ----------------------------------------- 2^0 items, "aa": ["a a","aa"] ------------------------------ 2^1 items, "aaa": ["a a a", "aa a", "a aa", "aaa"] - 2^2 items, ... } That explains the space. The time could be explained by the number of executions of the subproblems. Namely, in the worst case we'd have to make n calls of the helper function, and each one of those calls would have 2^n append calls made, leaving us with O(n * 2^n) https://leetcode.com/problems/word-br... --------------------------------------------------------------------------------------------------------------------------------------------------------------- Let's connect on LinkedIn!   / aleksmitrovic   Follow me on Medium!   / mitrovic.aleksandar   Questions or suggestions for new videos? Email me! babybear4812@gmail.com