LeetCode-in-Java
516. Longest Palindromic Subsequence
Medium
Given a string s, find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.
Constraints:
1 <= s.length <= 1000sconsists only of lowercase English letters.
Solution
public class Solution {
public int longestPalindromeSubseq(String s) {
char[] x = s.toCharArray();
char[] y = new StringBuilder(s).reverse().toString().toCharArray();
int m = x.length;
int n = y.length;
int[][] l = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
l[i][j] = 0;
} else if (x[i - 1] == y[j - 1]) {
l[i][j] = l[i - 1][j - 1] + 1;
} else {
l[i][j] = Math.max(l[i - 1][j], l[i][j - 1]);
}
}
}
return l[m][n];
}
}