Word Break Problem | Dynamic Programming | GeeksforGeeks

This video is contributed by Nideesh Terapalli.

Please Like, Comment and Share the Video among your friends.

Install our Android App:

If you wish, translate into local language and help us reach millions of other geeks:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)

[hsome]

Look no further folks. At the time of this comment this is by far the best video to watch to learn how to solve this problem because it doesn't immediately jump to an optimized solution without explaining how to get there.

[aakupsp]

Best explanation. It's so clear. I have watched other videos where they start with a dp matrix but don't explain the intuition behind it. This was an awesome explanation and I am never going to forget it.

[大盗江南]

thank you so much... this is the video i am searching for... the best video for this question. hope u could do more videos thank you!
very clear

[naveenkumars]

Very clear Explanation. Thank you so much :)

[shalsteven]

THIS IS THE BEST EXPLANATION VIDEO! HE CAN EXPLAIN IT FROM THE INTUITION UNTIL THE CODE 🔥🔥 other peole only explain it by jumping to code directly 😅

[johnTRAN]

10:30 You dont really need a map. A set would do. You can assume it always returns false If It finds a sub string you already did.

[nickharalampopoulos]

You are very good Nideesh! You don't have to be stressed! Best tutorial with the theory properly explained. Thank you.

[inspired_enough_to_grow_up]

Best video Sir... Crystal clear concept, Had been made much confusing by other tutorials.

[fahrizalsentosa]

Best explanation for DP about wordbreak. thank you very much

[christopherbrooke]

FABULOUS! Any video can't replace the explanation and conceptual simplicity this video has. TO_THE_POINT CONCEPTUAL VERY_CLEAR. Best video on this question I came across! Really loved it!

[AbhishekKumar-yvih]

Brute force approach time: O(2^n) because there are n+1 ways to partition a string of length n and each of the partition can be chosen in 2 ways.

[iamsks]

At 16:47 instead of s.substring(i, len) i think it should b s.substring(i, len-i) if u r going for c/c++. actually it depends on how u justify using the second parameter . if u mean the index value then its ok .. but in c/c++ it means the length u want after the index i .

[rikampalkar]

Hats off! Very well explained, concise and dense.

[shanmukhaditya]

This is the best explanation I saw for word break problem. Cheers man

[kirtimanmishra]

In the DP approach, it will be list.contains(s.substring(i, len-i))

[annafalvello]

Thanks for this! Great explanation, really helped me understand the DP solution.

[nutan]

There is some issue with the memoization code, it takes more time than the normal recursive approach.
You are putting in the map after the recursion call, so when recursion happens, map is still empty.
if (set.contains(s.substring(0, i)) && wbMemo(s.substring(i, s.length()), set, map, count)) {
map.put(s.substring(i, s.length()), true);
Let me know your thoughts.

[vibeStationPS]

Thank you so much for detailed explanation

[rahulagrawal]

s.substr(a, b), gives a sub string starting from index a and has length b. Note b is not the end index. s.substr(i, length) should be corrected to s.substr(i, len-i). Also why are we considering dp[0] as true? we have available "c" "od", "e", "x", any string of length zero isn't present in the given dictionary.
I think we should run a separate loop for dp[1] instead of dp[0] and then we can start generic loop.

[knpatel]

Thanks for the explanation. One thing I am trying to get my head around is why an empty string is considered found in the word dictionary? This pattern is seen in many dp problems and I am really confused about it.