Minimum Deletions , Form A Palindrome Geeks For Geeks
For Both Questions Code Is Same:
MINIMUM DELETIONS:
class Solution{
static int minimumNumberOfDeletions(String s1) {
StringBuilder sb=new StringBuilder();
sb.append(s1);
String s2=sb.reverse().toString();
int n=s2.length();
int t[][]=new int[n+1][n+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<n+1;j++){
if(i==0 || j==0){
t[i][j]=0;
}
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
t[i][j]=1+t[i-1][j-1];
}
else{
t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);
}
}
}
return n-t[n][n];
}
}
***********************************************************************************
FORM PALINDROME:
class Solution{
static int countMin(String s1)
{
StringBuilder sb=new StringBuilder();
sb.append(s1);
String s2=sb.reverse().toString();
int n=s2.length();
int t[][]=new int[n+1][n+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<n+1;j++){
if(i==0 || j==0){
t[i][j]=0;
}
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
t[i][j]=1+t[i-1][j-1];
}
else{
t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);
}
}
}
return n-t[n][n];
}
}
***********************************************************************************
TIME:O(N*N)[Geeks For Geeks Time:0.2/1.2 (For Minimum Deletions)]
[Geeks For Geeks Time: 0.2/1.1 (For Form A Palindrome)]
SPACE:O(N*N)
Thanks For Reading.😇
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment