Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
Input:
|
1 |
"bbbab" |
Output:
|
1 |
4 |
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:
Input:
|
1 |
"cbbd" |
Output:
|
1 |
2 |
One possible longest palindromic subsequence is “bb”.
Java Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
package com.javagists.learn.interview.questions; public class LongestPalindromeSubsequence { public int longestPalindromeSubseq(String input) { int[][] dp = new int[input.length()][input.length()]; for (int i = input.length() - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < input.length(); j++) { if (input.charAt(i) == input.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][input.length() - 1]; } public static void main(String[] args) { LongestPalindromeSubsequence longestPalindromeSubsequence = new LongestPalindromeSubsequence(); System.out.println(longestPalindromeSubsequence.longestPalindromeSubseq("bbbaabbgghj")); } } |
You can find the source code at github
why does your code not compile?
It compiles for me and you can find the file on github also. I have also added link to the github also