Word Break II - Leetcode 140 - Python 

Thank you! Outdated: I believe these sections should be Cache/Memo, not Backtracking as sections 2-3 8:37 - Backtracking Explanation 15:08 - Backtracking Coding

Build same DFS + Memoization like your flow but your explanation makes me realize I can totally remove the extra work like creating a preprocessed DP array that DP[i] checks s[i:] is breakable or not. If that was used, it could be added as a condition before Line 16 in your code. Again, thank you so much NC

i saw people brag about solving this problem but all thanks to you i was able to solve it like it was an easy Thank you bro ❤

Great work!

Thank you for this

Is there a reason you prefer to have state saved outside of your recursive function? Like in this case you have to append and pop from cur. I think it would be neater if made cur and argument `backtrack(i, cur + [w])` or something. On another note I am very grateful for what you're doing. You've helped me a lot

Isn't substring is an O(n) operation? So I think total time complexity is N * 2^n. What do you think?

Approach 1: "using up"letters, then use remainder" backtracking from where we're at Sln 2: BFS check if word fits at current index

Can you think of / give us a trie based solution? Topics suggested it can be done with trie?

So, word break 1 was a decision problem and word break 2 is an enumeration problem. Right?

First🎉

It's not really O(2^n), it is O(n*2^n) because you do s[i:j] which takes O(n) time in the worst case

Please add the difficulty of problems in the thumbnail or title

why have a nested function when you can use recursion on the given one...? For this specific problem, i found that the most basic(recursive) solution works just as good as a backtracking. but what do i know... def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: if not s : return [ ] res = [ ] for i in range(len(s)-1) : if s[:i+1] in wordDict : ans = s[:i+1] output = self.wordBreak(s[i+1:],wordDict) for out in output : if out : res.append(ans+" "+out) if s in wordDict : res.append(s) return res

Second🎉

I don't understand why I couldn't come to the first solution... I'm feel depresion

Btw word by word solution might be inefficient if we have same words 1000 times. Suppose string is "catscats" (or longer) and words are [cats, cats, cats.......] (1000 or 100000) So we need to have multiply big o with wordDict size. But if we do substring approach since we have set, we are safe

i chose xxx

Solution that uses your previous Word Break solution: class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: dp = [[False, []] for _ in range(len(s) + 1)] dp[len(s)] = [True, [""]] for i in range(len(s) - 1, -1, -1): for word in wordDict: if i + len(word)