36 Palindrome Partitioning Recursive
Вставка
- Опубліковано 30 вер 2024
- Palindrome Partitioning using Recursion
Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome.
Example:
“aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”.
PROBLEM STATEMENT LINK:www.geeksforge....
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
this series is giving so much . Not just improving our dp concepts but also thinking process ♥♥ I wish u stay happy
meanwhile raju to boss : chila chila ke scheme bata de :)))
😂😂😂😂😂😂😂😂😂😂
Jis din bhai ne Graph ke videos bana diye samajh lena us din duniya khatam ho jayegi
isliye wo din kabhi na aayega😜
isiliye Aditya ne graph series nhi banai . Thanks Aditya to save this world.😃
abhi bhi nhi banaya hai @@propubggamer2222
Mimimum partitions required for nitin = 0 :'):')
Yeah Buddy , you got right
yup return 0
in base case only
nitin ka naam change krna padega
@@sudhanshu4102 🤣🤣🤣🤣
@@sudhanshu4102 kyu Saale
I think this is a much better introduction to the MCM pattern than MCM itself. It's more intuitive to understand how we are paritioning inputs in all possible ways using this string example instead of MCM itself. Could be subjective, but just saying
Answer for "nitin" is 0 not 2. Because "nitin" is itself a palindrome. So no need to partition this. Otherwise your video is good to understand the logic.
I had never imagined that I would be solving leetcode/GFG hard problem in just one attempt. Thanks for this amazing playlist!
Lee Nitin after watching this video :-
Aabe itna bhi naam nahi karna thaa...
14:49 I can't believe what just happened! xD
35 of 50 (70%) done! Nicely explained!
Same here bro
What??
yo 10 months late :)
@@biswajitsahoo1456 ua-cam.com/video/lhckuhUxcgA/v-deo.html
@@biswajitsahoo1456 ok
Irony is the example Aditya took i.e. "nitin" is Palindrome and answer will be zero ....but the way he teaches is GREAT and we understood everything from wrong example
Yeah I realized it later too, I think I mentioned that in the next video
@@TheAdityaVerma hey bro, it would be nice to your viewers if you could provide us an update on how you are doing, it's been a while. Nothing but respect for you, for everything you did for thousands of upcoming engineers.
You did some God's work on this channel.
@@saugatgarwa6389 +1
@@TheAdityaVerma Please reply
@@saugatgarwa6389 actually my sixth sense 🙂 says.... Maybe he got married 😁 and that's the reason he doesn't get time for YT... (again its an assumption 😅)
Shouldn't the answer of your example be 0 because you took nitin which is a palindrome itself ?
yes, he admitted it in the next video of the dp playlist. the rest of the process and code is correct though.
Yeah my bad 😂 Shouldnt have taken nitin for an example😕
I was literally stuck there for like an hour was trying to figure out what is going on here watched the video multiple times...ahh silly me ;)
if anyone struggling in this q using java :-
Code :
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s = scn.next();
int ans = PalinPartitionRecursive(s);
System.out.println(ans);
}
public static int PalinPartitionRecursive(String s){
int i = 0;
int j = s.length()- 1;
if(i >= j){
return 0;
}
if(isPalindrome(s)){
return 0;
}
int ans = Integer.MAX_VALUE;
for(int k = i; k
short and easy to understand
public static int palindromicPartitioningRecursive(String s, int i, int j) {
if (i >= j || isPalindrome(s, i, j)) {
return 0;
}
int min = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int temp = palindromicPartitioningRecursive(s, i, k) + palindromicPartitioningRecursive(s, k + 1, j) + 1;
if (temp < min) {
min = temp;
}
}
return min;
}
public static boolean isPalindrome(String s, int i, int j) {
while (i
bro we are using dp to reduce time complexity and you are using substring function whose time complexity is O(N) and which is redundant
only passing string will do the work as we have kept pointers for defining string
Won't it be from i to k ?
It wont work, while checking isPalindrome you are always checking for whole string , instead of I to j.😅
My Working Java Recursive Code-
class Solution{
int palindromicPartition(String str)
{
// MCM- Dp- Recursion
return solver(str, 0, str.length()-1 );
}
boolean isPalindrome(String s, int i, int j){
while( i < j){
if(s.charAt(i) != s.charAt(j) ) return false;
i++; j--;
}
return true;
}
int solver(String s , int i, int j){
// base condition- // size 0 and 1 string are already palindrome - No partitioning
// whole string a palindrome then dont partition it.
if( isPalindrome(s, i, j)==true || i>=j )
return 0;
int minCuts = Integer.MAX_VALUE;
for(int k =i ; k
Please make a video for count of palindromic substring!🙏
Ps: BEST DP SERIES EVER!🌻
Yeah will try, cant promise anything rn tho tbh !!
Seriously, how many more sunflowers do you have ?! 😂😂
@@TheAdityaVerma well around 50 I guess😂 one for each of the 50 videos of this tutorial 🤷 might have some left for the rest too!
Haha Thanks !!
@@TheAdityaVerma bhai jaan matlab iss mahine kuch nahi aaega DP ka🙁🙁🙁🙁😭😭😭😭😭😭😭😭😭😭😭😭😭😭
I think we just have to apply the dp of longest palindromic substring and count all those values dp[i][j] > 1 && dp[i+1][j+1] == 0. Can't be precise though, we can get hints from dp table that gets created.
Can the first base condition be removed? coz anyways the isPalindrome method will return 0 when i ==j (i.e single character is always a palindrome) and so the i would never become greater than j , so first condition can be removed?
hey Aditya keep up the good work ,the way you teach can't be matched.Please make videos on graph as well.
Given the base condition for this question, wouldn't "nitin" return 0, as it is already a palindrome?
was searching for this comment!
yes it gives 0
I solved the qs even before watching this video bcoz I am consistently watching every videos from begining and it has developed the logic .Thanks a lot for such valuable content bro.
for sample case "nitin" the partition should be 0
Does he mention time and space complexity somewhere? Always difficult to calculate in recursion!
I would say for this, the palindrome calculation takes n
The for loop for k also takes n
And since we divide into 2 halves, that would lead to 2^n
Finally O(n.n.2^n)
@@aryamanpande5499 I think it will be O((n+n)*2^n) because neither the palindrome calculation nor the k for loop are nested within each other, they are independently executed pieces of code, so their complexities will add up instead of multiplying.
Bhai Bhai Bhai , gfg pe iss question ka code dekhke aisa laga ke keyboard tod du , par jab yeh video dekhi toh laga ek do keyboard aur khareed lu.
haa bhai khareed le yaar, meko b de dena ek, "r" key kaam ni kr rhi h meri 😂
@@TheAdityaVerma 😂😂
This series is just pure logic and thought process. No bullshit music, publicity, nor animations and. Love you, bro... .....
no aman dhattarwal was harm during this comment.
I agree with you!!
Biggest trick is if a string is palindrome then return 0 . Was stuck there when tried without starting video. I think writing the pseudo code on paper with logic can help a lot . Thanks Aditya .
Why then in case of the input - nitin (which is already a palindrome) - the output is 2 and not 0?
@@d1vyanshu output is 0 in case of nitin, as when solve function will be called, isPalindrome() will already return 0
#C++ code
#include
using namespace std;
bool isPalindrome(string s,int i,int j){
while(i=j)
return 0;
if(isPalindrome(s,i,j))
return 0;
int mn = INT_MAX;
for(int k=i;k s;
cout
Sir in Longest Palindromic Substring, do we follow the same output format that we have followed in the MCM question?
Was this the 27th video? It's unavailable now
Please also include Time complexity analysis , i find it difficult to do for recursive problems.
Nitin mere coaching wale maths teacher ka name tha
17:03 I guess the partition when k=j is correct because then 1st partition will be entire string [i, k=j] and second partition will be [k+1(j+1), j] i.e. empty. So 1st partition full string 2nd partition empt. And for "nititn" op should be 0 ans it is already palindrome so min number of partition is 0 not 2.
No, It will get stuck in recursion calls
the IsPalindrome() check will take care of the strings like "nitin" i.e. fully palindrome strings, and returns 0 from there only.
so for "nitin", the FOR loop will never execute
we dont have to find minCuts for string between i to k we can just check if string from i to k is palindrome then minCuts between them is 0 see below code
int dp[501][501];
bool isPalindrome(string str,int i,int j){
while(i=j || isPalindrome(str,i,j)) return 0;
int minCuts=INT_MAX;
if(dp[i][j]!=-1) return dp[i][j];
for(int k=i;k
Can you please explain your approach once? I mean, why are you checking whether the substring from i to k is a palindrome. Would be glad if you reply :)
Means you can use only 1D array rather than 2D array as only i is changing and not j.
sir for every substring can we calculate LPsubstring and put a partition before and after it and call LPS again for remaining string
will this work?
🌻 please graphs pada dho
How can we print it..... will it be having a relation to print MCM ?
Any one with mcm dp variation (top down) ??
Respected Sir, The answer given in the Description is wrong...
It should be 3 and not 5..
I verified with your code...
a | babbbab | babab | a
Best dp videos on UA-cam. Please make videos on graph also
Vho junior mea hi tho nahi hu bhiaya mea 3rd year mea hu xD
"NITIN" is already a palindrome string .... then why we need to partitions ?
bool isPalindrome(string s,int a,int b)
{
for(int i=a;i
Imagine the feel that real nitin gets when he watches this video.
i also knew one nitin, but he was annoying af
😂😂😂😂😂😂😂😂 The Nitin I knew, was too 😂😅
@@TheAdityaVerma ahya haya bhiay khel gya
Ur flirting game is on par with his coding skills. Calm down girl
@@mujtabaarfat717 it's a shame that my comments of appreciation looks like flirting to you.
I don't remember saying anything *flirty*, just because i enjoyed his videos, i commented nice things and I started getting stupid comments like yours.
Pls get a life , u guys really need one.
@@jayshree7574 He already has a life .. That is why he was able to comment .. If he would have been dead then how could he have been replied ?? How can u decide someone's existence .. ?? How ??
From which college and in which year , you completed your graduation bhaiya??
Just an eagerness!!
He is from MANIT bhopal!!!
I think 2019 batch
bhaiya... 8:21 correct ur typo
k=i ----> j-1
k=i+1 ----> j
"nitin" word itself palindrome so it will return 0 not 2. btw good concept
Kisi aur dost ko yaad kar lete @aditya.! Us ek aur dost ko bhi acha lgta aur Hame bhi 😅😛
jor jor se bolke sbko scheme bta diya 💖💖
Nitin vale me example me 0 aana chahiye n. Qki bina partition ke bhi vo palindrome hi h
whi to nitin to pehle se palindrome hai
@@abhinavprakash1918 next video me clear kar diya gaya h
bro I think the answer for nitin string will be 0 because nitin itself is a palindrome
It's nithin bro, ok some people write our name as nitin it's totally ok
@Aditya Verma a great cheers to you and your work, i have been following ur playlist and i must say that its the best playlist for dp. I tried this question on gfg but i am getting tle. Can you or anyone else help ? my code is :
static int t[][];
static Map mp;
static int palindromicPartition(String str)
{
mp= new HashMap();
t= new int[str.length()+1][str.length()+1];
for(int i=0;i
nitin is already a palindrome so it's output should be 0 instead of 2.
agree answer should have been 0
bhai maacha diy
thanx a lot bhaiya g
Bhaiya Ek Video Longest Increasing Subsequence p bnaa do please
striver ke dekh le nlog(n) wali aache video hai
this has O(n^3) t.c. which does not work in most ides
This solution will give TLE in leetcode.
this approach is showing tle in gfg
bhaiya prr jo aapne string liya tha wo to already ek palindrome h i.e. nitin
This approach is very slow iterative one is much faster
is dis english? lol i hear basically sometimes
javascript solution :- function isPlaindrom(string) {
let j = string.length - 1
for(let i = 0; i= j) return 0
if(isPlaindrom(string)) return 0
let ans = Number.MAX_SAFE_INTEGER
for(let k = i; k
All of your videos are uploaded on 5th-6th Feb. Did you record day and night for this series ?
inactive for 4 months am afraid if he will upload DP topics regarding Trees and Graph or not :(
Voice of the video is very low.
kadanes algo videos??
Can anyone help me out how to print all possible pallindromic partitions of a string?
find all substrings and apply check palindrome fn and print them.
@@shubhivdogra3412 No , we can infact do a recursive call to make partitions without having to create all substrings and checking which of them are palindromes, Striver has made a video about it.
yeah this is way harder of a question imo
Hello bhai!! Nitin here, Thanks for taking my name. :)
Iss baat k liye Tumhe puruskar Diya jata hai😂😂
God of DP
# recursive case:
# recursive version
def isPalindrome(S):
return S[::-1] == S
def Solve1(str1,i,j):
min1 = float('inf')
if i >= j or isPalindrome(str1[i:j+1]) :
return 0
for k in range(i,j,1): # i.e for(int i = k; k
Sir in for loop temp=1+solve(s,k+1,j) is only needed know like if we check , first recursive call seems unwanted, can you please correct if I am wrong
Can you make graph and trie series as well in hindi
please humble request 😢😢😢😢😢😢
Really well explained but this code will give tle in gfg or leetcode. And if you have figured out tle problem, it will give memory exceed verdict. I got to know the correct method 10 days after i watch this video. I just wonder why you did not described the most efficient method in the start?? Its like we are giving time watching this video, but it is of no help when we solve it. Anyways...thanks for beautifully explaining DP.
Don't you guys think that example used in this video which is "nitin" is already palindrome? So answer should be 0 not 2.....or i am missing something. Although my concepts are clear from this video but i shared this thing to increase my knowledge!
Working Java Recursive Code-
class Solution{
int palindromicPartition(String str)
{
// MCM- Dp- Recursion
return solver(str, 0, str.length()-1 );
}
boolean isPalindrome(String s, int i, int j){
while( i < j){
if(s.charAt(i) != s.charAt(j) ) return false;
i++; j--;
}
return true;
}
int solver(String s , int i, int j){
// base condition- // size 0 and 1 string are already palindrome - No partitioning
// whole string a palindrome then dont partition it.
if( isPalindrome(s, i, j)==true || i>=j )
return 0;
int minCuts = Integer.MAX_VALUE;
for(int k =i ; k
Video is Awesome. But 'NITIN' itself is palindrome. It should return 0 partition
nICE oNE
Nitin will return 0 as it is already a palindrome.
PS: BEST DP SERIES EVER!!
bhaiya... 8:21 correct ur typo
k=i ----> j-1
k=i+1 ----> j
Why do we require the if statement?
How can mn be greater than INT_MAX
Isnt the voice too low.?
we are writing mn inside the solve fxn, it will keep updating everytime. we don't want that.
LeetCode Palindrome Partitioning II
class Solution {
public int minCut(String s) {
Integer[][] dp = new Integer[s.length() + 1][s.length() + 1];
return mcm(0, s.length() - 1, s, dp);
}
public int mcm(int start, int end, String s, Integer[][] dp) {
if (start >= end) {
return dp[start][end] = 0;
}
if (dp[start][end] != null) {
return dp[start][end];
} else if (palin(s, start, end)) {
return dp[start][end] = 0;
}
int min = Integer.MAX_VALUE;
for (int i = start; i < end; i++) {
if (palin(s, start, i)) {
int partitions = 1 + mcm(i + 1, end, s, dp);
min = Math.min(min, partitions);
}
}
return dp[start][end] = min;
}
public boolean palin(String s, int l, int h) {
while (l < h) {
if (s.charAt(l) != s.charAt(h)) {
return false;
}
l++;
h--;
}
return true;
}
}
what a good explaination i babbar bhaiya didn't taught this concept
can someone explain why mn is not static? I mean why it isn't static int mn=INT_MAX;
can the same concept be used for Word Break problem?
javascript perfectly worked solution :-
function isPalindrome (string,i,j) {
for(i; i= j){
return 0
}
if(isPalindrome(string,i,j)){
return 0
}
let min = Number.MAX_SAFE_INTEGER
for(let k = i; k
one more thing if we choose k to go till j then we will stuck in the loop .. again calling solve(arr,i,j) // where k ==j
Am I the only one who has audio issues(Getting very low audio)?
leetcode.com/problems/palindrome-partitioning-ii/
Leetcode problem Link
Very nice video brother.
I have a doubt that a string having no elements and a string having only one element is also a palindromic string. So can we omit the first if statement ? because that condition is already included in the 2nd if statement.
Nop ..
We also need to check i>j case anyway cz if the given string is empty or consists of one character then it would result in i==j case but not i>j case .
So we must check i>j case initially ..need not to ignore that:)
Hope it helps
the volume was low then it got lower
crazy good tutorials tho
can any 1 tell me where to learn this kind of recursion,i m really struggling with this sort of recursion
what will be recursive complexity ??
Better take min=length of string. . (While initialisation)
Sir but "nitin" string toh khud ek palindrome hai toh output main toh zero return karega
nitin is already a palindrome so ans should be zero for this case
The most unique palindrome
nayan
नयन
নয়ন
નયન
ନୟନ
משטשמ
eye (meaning of nayan)
it probably is a palindrome in many of the Indian and non-Indian languages
Also the name of this account 😱😱😱😱😱😱😱😱😦😦😦😮😮😮😮😮😮
nitin is also palindrome then why do we need to partitioning of this???
String nitin itself a palindrome. So rec will stop and result will be 0 right?
@Himalayan drifter no ...
Same doubt
where is the mcm video that he was mentioning?
ye 29 dislikes waalo ko zinda pakadna hai😂😂
thanks sir
this code is giving me output 1 for every non-palindromic string.
pass min with the function like this solve(String s,int i,int j,int min)
But when theres always a palindromic strijg like nitin, won't then ans be 0 already ?
@gauravmathur4082 I'm also facing the same problem ,did you find the solution?
I also tried solving the call stack for recursive calls and it is always giving the value one(1) for every input string which is non palindromic string and does not contain any palindromic substring
For eg "man"
Output is 1
yaaar ye bande ko milna hain kitna assni se batata hain