Word Break II - Leetcode 140 - Python

0:00 - Read the problem
0:39 - Backtracking Explanation
6:02 - Backtracking Coding
8:37 - Memoization Explanation
15:08 - Memoization Coding

leetcode 140

#neetcode #leetcode #python

[rostyslavmochulskyi]

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

[tusov]

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

[pastori]

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 ❤

[MappyNeb]

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) <= len(s) and s[i:i + len(word)] == word:
if dp[i + len(word)][0]: # Check if the rest of the string can form valid sentences
# Create new sentences by appending the current word to each sentence from dp[i + len(word)]
new_sentences = [word + ("" if sentence == "" else " " + sentence) for sentence in dp[i + len(word)][1]]

dp[i][0] = True

return dp[0][1]

[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

[thelindayz]

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-xiyy]

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

[antondonohue]

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

[MehmetDemir-xiyy]

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, (1000 or So we need to have multiply big o with wordDict size.

But if we do substring approach since we have set, we are safe

[Nishit_]

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

[janesun]

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

[aashishbathe]

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

[ritikaagrawal]

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

[momenwadood]

Please add the difficulty of problems in the thumbnail or title