FilesExpand file tree

 master

/

LongestPalindromicSubsequence.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (51 loc) · 2.03 KB

 master

/

LongestPalindromicSubsequence.java

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (51 loc) · 2.03 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

package test;

import java.io.*;

import java.util.*;

/**

* Algorithm explanation https://www.educative.io/edpresso/longest-palindromic-subsequence-algorithm

*/

public class LongestPalindromicSubsequence {

public static void main(String[] args) {

String a = "BBABCBCAB";

String b = "BABCBAB";

String aLPS = LPS(a);

String bLPS = LPS(b);

System.out.println(a + " => " + aLPS);

System.out.println(b + " => " + bLPS);

}

public static String LPS(String original) throws IllegalArgumentException {

StringBuilder reverse = new StringBuilder(original);

reverse = reverse.reverse();

return recursiveLPS(original, reverse.toString());

}

private static String recursiveLPS(String original, String reverse) {

String bestResult = "";

// no more chars, then return empty

if (original.length() == 0 || reverse.length() == 0) {

bestResult = "";

} else {

// if the last chars match, then remove it from both strings and recur

if (original.charAt(original.length() - 1) == reverse.charAt(reverse.length() - 1)) {

String bestSubResult =

recursiveLPS(

original.substring(0, original.length() - 1),

reverse.substring(0, reverse.length() - 1));

bestResult = reverse.charAt(reverse.length() - 1) + bestSubResult;

} else {

// otherwise (1) ignore the last character of reverse, and recur on original and updated

// reverse again

// (2) ignore the last character of original and recur on the updated original and reverse

// again

// then select the best result from these two subproblems.

String bestSubResult1 = recursiveLPS(original, reverse.substring(0, reverse.length() - 1));

String bestSubResult2 = recursiveLPS(original.substring(0, original.length() - 1), reverse);

if (bestSubResult1.length() > bestSubResult2.length()) {

bestResult = bestSubResult1;

} else {

bestResult = bestSubResult2;

}

}

}

return bestResult;

}

}