Q31 Longest Palindromic Substring - LeetCode
Sun Mar 26 2023 09:48:18 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public String longestPalindrome(String s) {
/* Q30 dp playlist , similiar to Q22
the last true cell will be the LPS with length gap +1
which can be found by substring(i , j+1)
*/
//making 2d dp
int n = s.length();
String ans = "";
boolean dp[][] = new boolean[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] = true;
else if(gap == 1)
dp[i][j] = s.charAt(i)==s.charAt(j) ? true : false;
else{
if(s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i+1][j-1];
//else default value is already false
}
//storing the substring of the last true value
if(dp[i][j] == true)
ans = s.substring(i,j+1);
}
}
return ans;
}
}
content_copyCOPY
https://leetcode.com/problems/longest-palindromic-substring/
Comments