Q29 Longest Palindromic Subsequence - LeetCode 516
Sun Mar 26 2023 07:52:04 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int longestPalindromeSubseq(String s) {
/* Q29 of dp series , gap1 strategy
*/
//making 2d dp array, S&m - every cell denotes LPS of that string
int n = s.length();
int[][] dp = new int[n][n];
for(int gap = 0 ; gap < n ; gap++){
for(int i = 0 , j = gap; j < n ; i++ , j++){
if(gap == 0)
dp[i][j] = 1; //for 1 character string LPS = 1
//for 2char string , LPS = 2 if c1=c2 else LPS = 1
else if(gap == 1)
dp[i][j] = s.charAt(i)==s.charAt(j) ? 2 : 1;
//i denotes prefix , j denotes suffix
else{
//if c1 == c2 , LCS of middle part + 2 for both chars
if(s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i+1][j-1] + 2;
//else max of (prefix , suffix)
else
dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]);
}
}
}
// for(int i = 0 ; i < n ; i++){
// for(int j = 0 ; j < n ;j++)
// System.out.print(dp[i][j] + " ");
// System.out.println();
// }
return dp[0][n-1];
}
}
content_copyCOPY
https://leetcode.com/problems/longest-palindromic-subsequence/
Comments