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.
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
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.
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
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/
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
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.
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.
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"]]
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.
+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.
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.
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
Awesome 15 min explanation
Thanks Harshdeep!
you are the only 1 DP solution I really understand! Thank you!
Thanks Ho Yin Li!!
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.
Why is the brute force n^3 ?
All the string partition possibilities aren't 2^(n-1) ? Or am I missing something?
Thanks!
I dont get it either...Did u figure this out?
actually brute force here refers to another DP approach which is not as good as this DP approach.
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
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/
Thanks brother, this video helped me a lot🙌. Keep doing 👍
😊
thank you, sir. I was trying to get it from many resources, finally, I got it through this video
you deserve more subscriber man!
🥺
God Level Explanation. Thanks bro was finding this whole day !
Wow! Thanks Aniket!
@@IDeserve Bro u truly deserve it. I guess that's why u named d channel IDeserve😂....Jokes apart keep uploading great content 😊 ATB
Thanks bro and keep posting more videos they are helpful !!
Thank you sir for this approach , hope for such great content in future too .
Please upload more why did u stopped
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
Best Explanation ever. Sir plz provide solutions for problem in leetcode medium and hard questions
Tried to print the substrings ... anyone managed to get the minimum substrings as a list instead ?
Best explanation 👍
Sir your videos are always helpful, Just got to search for that ideserve logo, and my doubts are clear.
Thanks for your kind words Bhavuk!
Instead of keeping boolean matrix it is easy to count the minimum cut in matrix itself.....
then return top right corner value
Nice Explanation
this is O(n^3) solution right?
Best explanation of this problem 🎈⚡⚡😀
Thanks Mohak!
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.
Amazing , please keep adding more probs . Is there any book that we should refer to look out for such questions ? Any recommendation . Thanks .
solve leetcode or use ctci for questions
i don't think there is brute force way of o(n^3) please check
I think, by Brute force they mean calculating min cut for every possible substring in the string.
That one is also based on DP
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.
Thank you!
WOW, that was helpful. Thanks
Excellent work !
great tutorial! thanks a lot for your help
Thanks!
@@IDeserve why have you stopped uploading?
thank you ideserve.
Nice explanataion..!!
Thanks Sushil!
Well explained..
Its Awesome 🔥🔥
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"]]
Sir you are awsome
Karthik you are awesome 😊
explained nicely :)
Thank you so much Yash for your kind words :)
Awesome.
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.
Nice, thank you :)
+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.
Yes, i've been watching a lot of videos of yours :) they're all too helpful
+shaival chokshi
Thanks a lot for appreciating!