Longest Palindromic Subsequence Geeks For Geeks And LeetCode And InterviewBit
class Solution
{
public int longestPalinSubseq(String s1)
{
StringBuilder sb=new StringBuilder();
sb.append(s1);
String s2=sb.reverse().toString();
int n=s1.length();
return cal(s1,s2,n);
}
public int cal(String a, String b, int n){
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=01;i<n+1;i++){
for(int j=01;j<n+1;j++){
if(a.charAt(i-1)==b.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 t[n][n];
}
}
TIME:O(N*N)[Geeks For Geeks Time: 0.2/1.3]
SPACE:O(N*N)
***********************************************************************************
LEETCODE:
class Solution {
public int longestPalindromeSubseq(String s) {
int n=s.length();
int t[][]=new int[n+1][n+1];
StringBuilder sb=new StringBuilder();
sb.append(s);
String s2=sb.reverse().toString();
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=01;i<n+1;i++){
for(int j=01;j<n+1;j++){
if(s.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 t[n][n];
}
}
TIME:O(N*N)[LeetCode Time: 74ms faster than 34.92%]
SPACE:O(N*N)[LeetCode Memory: 49.2MB less than 66.22%]
***********************************************************************************
InterviewBit
Thanks For Reading.😇
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment