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
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
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
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)
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
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.
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
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
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
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
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 ❤
Isn't substring is an O(n) operation? So I think total time complexity is N * 2^n. What do you think?
yeah but N can be max up to 20 so N*2^n will also work fine
Approach 1: "using up"letters, then use remainder" backtracking from where we're at
Sln 2: BFS check if word fits at current index
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
Can you think of / give us a trie based solution? Topics suggested it can be done with trie?
Store all the words in the trie and then dfs?
So, word break 1 was a decision problem and word break 2 is an enumeration problem. Right?
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)
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
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.
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
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
Great work!
Thank you for this
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
I don't understand why I couldn't come to the first solution... I'm feel depresion
lol same it was fairly simple and easy
Please add the difficulty of problems in the thumbnail or title
First🎉
Second🎉
i chose xxx