Word Break II - Leetcode 140 - Python

[@rostyslavmochulskyi159]

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

[@pastori2672]

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 ❤

[@tusov8899]

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

[@deathbombs]

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

[@Mappy13Neb]

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)

[@MehmetDemir-xi3yy]

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

[@ItachiUchiha-xi7ox]

yeah but N can be max up to 20 so N*2^n will also work fine

[@thelindayz2087]

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

[@MehmetDemir-xi3yy]

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

[@1vader]

The description says all given words are unique. Also, even if not, you can use a set with that approach as well. Though checking 1000 words vs max 20 substrings is still less efficient in practice but I guess not in big O.

[@MehmetDemir-xi3yy]

Thank you. Yes I read the constraints but I was talking about general comparison between them. As you said 1000 words is less efficient and it depends on string length and word dict size. If word dict size are small and unique, word by word is efficient than substring approach but if string length is small and word dict size are big or not unique then substring approach is more efficient

[@antondonohue8943]

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

[@janesun3701]

is the join function also o(n) since at worst we'd join every character with a space?

[@johnniewalkerjohnniewalker2459]

Great work!

[@aashishbathe]

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

[@sarthakjohnsonprasad3909]

Store all the words in the trie and then dfs?

[@MP-ny3ep]

Thank you for this

[@Nishit_369]

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

[@Antinormanisto]

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

[@rahulnegi456]

lol same it was fairly simple and easy

[@chien-yuyeh9386]

First🎉

[@ritikaagrawal769]

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

[@momenwadood1342]

Please add the difficulty of problems in the thumbnail or title

[@pranithtirumalsetti1453]

Second🎉

[@nikhil199029]

i chose xxx