ฝัง
- เผยแพร่เมื่อ 30 ก.ย. 2024
- Given a String S, find the minimum number of cuts required to separate the string into a set of palindromes.
This video explains the solution to palindrome partition problem using dynamic programming.
Source code link:-
github.com/IDe...
Website: www.ideserve.co.in
Facebook: / ideserve.co.in
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.
Thanks brother, this video helped me a lot🙌. Keep doing 👍
😊
Nice Explanation
Thank you!
you deserve more subscriber man!
🥺
Thanks bro and keep posting more videos they are helpful !!
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
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.
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/
Please upload more why did u stopped
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
Instead of keeping boolean matrix it is easy to count the minimum cut in matrix itself.....
then return top right corner value
Best Explanation ever. Sir plz provide solutions for problem in leetcode medium and hard questions
Thank you sir for this approach , hope for such great content in future too .
you are the only 1 DP solution I really understand! Thank you!
Thanks Ho Yin Li!!
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.
WOW, that was helpful. Thanks
Best explanation 👍
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
thank you, sir. I was trying to get it from many resources, finally, I got it through this video
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!
Awesome 15 min explanation
Thanks Harshdeep!
thank you ideserve.
Its Awesome 🔥🔥
Excellent work !
Best explanation of this problem 🎈⚡⚡😀
Thanks Mohak!
Tried to print the substrings ... anyone managed to get the minimum substrings as a list instead ?
Well explained..
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"]]
Nice explanataion..!!
Thanks Sushil!
great tutorial! thanks a lot for your help
Thanks!
@@IDeserve why have you stopped uploading?
Sir you are awsome
Karthik you are awesome 😊
this is O(n^3) solution right?
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!
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.
explained nicely :)
Thank you so much Yash for your kind words :)