LPS algorithm

matteomessmer · matteomessmer · commit 1bf0fe05a228 · 2020-10-09T10:53:39.000+02:00
diff --git a/DynamicProgramming/LongestPalindromicSubsequence.java b/DynamicProgramming/LongestPalindromicSubsequence.java
@@ -0,0 +1,58 @@
+package DynamicProgramming;
+import java.lang.*; 
+import java.io.*; 
+import java.util.*; 
+  
+/**
+ * @author Matteo Messmer https://github.com/matteomessmer
+ */
+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);
+    }
+
+    private static String LPS(String original) {
+        StringBuilder reverse = new StringBuilder(); 
+        reverse.append(original); 
+        reverse = reverse.reverse();
+        return recursiveLPS(original, reverse);
+    }
+
+    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;
+    }
+}
