top of page
Caută
Poza scriitoruluioanaunciuleanu

Longest Palindromic Subsequence in JAVA

Given a sequence of letters, find the length of the longest palindromic subsequence in it.


Input: "GREATPROGRAMMING" Output: 7 Explanation: The longest palindromic subsequence is: “GARORAG” or “GARGRAG


Solution:


1. public static void main(String[] args) { 2. String sequence = "GREATPROGRAMMING"; 3. int sequenceLength = sequence.length(); 4. int[][] dynamicProgramming = new int[sequenceLength][sequenceLength]; 5. for (int[] arr : dynamicProgramming) { 6. Arrays.fill(arr, -1); 7. } 8. 9. System.out.printf("The length of the longest palindromic subsequence is: %d", 10. longestPalindromicSubsequence(sequence.toCharArray(), 0, sequenceLength - 1, dynamicProgramming)); 11. } 12. 13. static int longestPalindromicSubsequence(char[] sequence, int i, int j, int[][] dynamicProgramming) { 14. 15. if (i == j) { 16. return dynamicProgramming[i][j] = 1; 17. } 18. 19. if (sequence[i] == sequence[j] && i + 1 == j) { 20. return dynamicProgramming[i][j] = 2; 21. } 22. 23. if (sequence[i] == sequence[j]) { 24. return dynamicProgramming[i][j] = longestPalindromicSubsequence(sequence, i + 1, j - 1, dynamicProgramming) + 2; 25. } 26. 27. return dynamicProgramming[i][j] = Math.max(longestPalindromicSubsequence(sequence, i, j - 1, dynamicProgramming), longestPalindromicSubsequence(sequence, i + 1, j, dynamicProgramming)); 28. } 29.

1 afișare0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no...

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Kommentare


bottom of page