Palindrome Partitioning Dynamic Programming

[@blatogh1277]

that makes my life easier. In my opinion, to test whether is a palindrome, we just need to have a test function to go over the substring and determine whether this substring is palindrome or not.

[@hoyinli7462]

you are the only 1 DP solution I really understand! Thank you!

[@IDeserve]

Thanks Ho Yin Li!!

[@gyanasahu1006]

There is a better approach to constructing this dp table. The flaw here is we are constructing row by row and we have to look at row + 1 for updating dp[row][1..]. Do it by length, which is more intuitive. Below is the code: for(int i=1; i

[@34_harshdeepraghuwanshi98]

Awesome 15 min explanation

[@IDeserve]

Thanks Harshdeep!

[@anmoljain5846]

thank you, sir. I was trying to get it from many resources, finally, I got it through this video

[@IDeserve]

Dear Friends, If you like our content and would like us to continue making great content for you, please spread the word about IDeserve. A share/appreciation from you on social network would mean the world to us! Also, do like our Facebook page: facebook.com/IDeserve.co.in :) Thanks, -Team IDeserve.

[@aadityasharma9790]

you deserve more subscriber man!

[@IDeserve]

🥺

[@aniket7512]

God Level Explanation. Thanks bro was finding this whole day !

[@IDeserve]

Wow! Thanks Aniket!

[@aniket7512]

@@IDeserve Bro u truly deserve it. I guess that's why u named d channel IDeserve😂....Jokes apart keep uploading great content 😊 ATB

[@himanshusrihsk4302]

Best Explanation ever. Sir plz provide solutions for problem in leetcode medium and hard questions

[@bhavukgarg3619]

Sir your videos are always helpful, Just got to search for that ideserve logo, and my doubts are clear.

[@IDeserve]

Thanks for your kind words Bhavuk!

[@NitinSingh-hk3vy]

Thanks brother, this video helped me a lot🙌. Keep doing 👍

[@IDeserve]

😊

[@pathikritchanda62]

Thank you sir for this approach , hope for such great content in future too .

[@namanvijay3514]

Best explanation 👍

[@Ice-2706]

Thanks bro and keep posting more videos they are helpful !!

[@sujan_kumar_mitra]

Nice Explanation

[@karthiknedunchezhiyan5136]

Instead of keeping boolean matrix it is easy to count the minimum cut in matrix itself..... then return top right corner value

[@lifehacks9450]

Please upload more why did u stopped

[@mohakchaudhary1981]

Best explanation of this problem 🎈⚡⚡😀

[@IDeserve]

Thanks Mohak!

[@haimbendanan]

Why is the brute force n^3 ? All the string partition possibilities aren't 2^(n-1) ? Or am I missing something? Thanks!

[@11m0]

I dont get it either...Did u figure this out?

[@neerajjoshi9493]

actually brute force here refers to another DP approach which is not as good as this DP approach.

[@manjesh80]

Its n^2 + n^2 . === n^2 ... compare to other approaches .. which is n^3 If n = 1000 n^2 ==> 1000000 ==> 1 Million n^3 == 1000000000 ==> 1 Billion n^2 + n^2 ==> 2 Million

[@shiwanggupta8608]

Actually its not brute force..using brute force it would be O(n*2^n) using dynamic programming we can achieve O(n^2) using different approach www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/

[@anonymoussloth6687]

Brute force would be 2^n because u r not checking all substrings. U r checking all valid cuts. You have n positions where you can place the cut and you have two options at each position to cut it or not cut it

[@ameyapatil1139]

Excellent work !

[@harveylastname1523]

The table of 2D information is not used all, you can save the integer but not boolean only.Save the min(T[i][j] = 1+ Min(T[i][k] , T[k][j-1]) to the table 2D, so the T[i][j] is the answer.

[@Vinny254]

Tried to print the substrings ... anyone managed to get the minimum substrings as a list instead ?

[@chrisogonas]

WOW, that was helpful. Thanks

[@kushal1]

Great video... Just one thing I didn't get the intuition behind dp[j] + 1. Difficult to understand. Dry run makes little more sense but still. Could have been explained better.

[@falakk22]

Amazing , please keep adding more probs . Is there any book that we should refer to look out for such questions ? Any recommendation . Thanks .

[@vorasagar7]

solve leetcode or use ctci for questions

[@rishitgupta7848]

Thank you!

[@SurendraSingh-hp9gk]

thank you ideserve.

[@08JuHan]

great tutorial! thanks a lot for your help

[@IDeserve]

Thanks!

[@sajalagrawal1430]

@@IDeserve why have you stopped uploading?

[@varunnarayanan8720]

Well explained..

[@justanaverageguy4739]

this is O(n^3) solution right?

[@Sushil2874]

Nice explanataion..!!

[@IDeserve]

Thanks Sushil!

[@vicentefelipe4287]

loved this video, super helpful, can you do Palindrome Partitioning, where you return all possible palindrome partitioning of s. For example, given "aab". return [["aa","b"], ["a","a","b"]]

[@mkay7800]

Its Awesome 🔥🔥

[@karthiksharma8720]

Sir you are awsome

[@IDeserve]

Karthik you are awesome 😊

[@varunkunchakuri1204]

i don't think there is brute force way of o(n^3) please check

[@pownarthithimiridayasagar2229]

I think, by Brute force they mean calculating min cut for every possible substring in the string.

[@bipul2138]

That one is also based on DP

[@lemonginger001]

explained nicely :)

[@IDeserve]

Thank you so much Yash for your kind words :)

[@ZiiiP2142]

Awesome.

[@IDeserve]

Thanks primaltare for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@shaivalchokshi3424]

Nice, thank you :)

[@IDeserve]

+shaival chokshi Thanks a lot for your words! It is very encouraging to hear such comments! We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like algorithm visualizations, learn together and many more coming soon. We are uploading new topics everyday. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@shaivalchokshi3424]

Yes, i've been watching a lot of videos of yours :) they're all too helpful

[@IDeserve]

+shaival chokshi Thanks a lot for appreciating!