WORD BREAK | PYTHON | LEETCODE # 139

In this video we are solving a popular Amazon and Facebook interview question: Word Break. This is an interesting question because it seems quite complex to implement but the solution makes a lot of sense if you intuitively try to work through it.
We'll be solving it with a clean BFS solution that should hopefully make a ton of sense once you see how things are done.

[@landocodes]

Bro I love how honest you are!! It really really makes you stand out against all of the other CZcamsrs who provide leetcode solutions.
Keep it up man I’m a fan 🙌🏾

[@crackfaang]

Haha yea I like to keep it real, especially with the shit questions.

[@hennessyypapi]

thank you for everything. out of all the major youtubers, your explanations resonate the most with me.

[@alabamatabasco3418]

"Dynamic programming is shit"... sirens in the background lmao

[@harshithamaripally3776]

your explanations resonate the most with me.

[@crackfaang]

Thanks for the kind words mate! Glad to have you with us on the channel :)

[@eduardoignacioroblessosa6349]

that was a pretty intuitive solution, just beautiful

[@galinabakman9901]

great solution

[@fadsa342]

I used recursion with memoization to solve the problem but your solution is a lot easier to grasp if I'm being honest. Out of curiosity can BFS be applied to most problems that you'd normally use DP or recursion for? And do you have any resources for getting better at determining space/time complexity?

[@crackfaang]

I generally stay away from anything DP because I find the concept total bullshit. I will when necessary use recursion + memoization to get around standard DP problems. I always look for the DFS/BFS solution where it exists because my brain can very easily understand and code those, whereas DP is too much of a mind-bend.
In terms of getting better at time/space complexity analysis, it really comes down to repetition and understanding the basics of what operations are what which then stack on top of each other when applied in a larger algorithm

[@akjenksgamer1266]

Thank you! I don't like dp either so i'm glad i found another solution

[@crackfaang]

Haha yea I try to avoid DP at all costs. It’s such a stupid and horrendous way of solving these problems

[@samvaidya1987]

@4:21 - why do you think we have to process "leet" again?

[@lonen3rd]

Because a word can exist multiple times in s e.g. s = "applepenapple"

[@abbyh2879]

It works but I am not sure why BFS?

[@crackfaang]

Well if you can do the brute force solution but you aren't getting the job. So it's now a choice between DFS, BFS, and dynamic programming. I personally fucking hate DP and don't code any solutions in that garbage lol. And I think any time you have a choice between BFS and DFS I would choose BFS because you don't have to worry about recursion and stack overflow. And a lot of the times if you code up the recursive solution they ask for the iterative afterwards. It's up to you what way works best for you. I just went with BFS because it's my preferred solution and the one I can explain the best :)

[@abbyh2879]

@@crackfaang Thanks for the reply, makes sense. I hate DP too, that's the reason I am subscribed to your channel, because I can always find non-DP solutions here.