Longest common subsequence: Difference between revisions

Content deleted Content added

Inline

@@ Line 268: / Line 268: @@
 This is not a particularly fast algorithm, but it gets the job done eventually. The speed is a result of many recursive function calls.
 <lang java>public static String lcs(String a, String b){
-    if(a.length() == 0 || b.length() == 0){
+    int aLen = a.length();
+    int bLen = b.length();
+    if(aLen == 0 || bLen == 0){
         return "";
-    }else if(a.charAt(a.length()-1) == b.charAt(b.length()-1)){
+    }else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
-        return lcs(a.substring(0,a.length()-1),b.substring(0,b.length()-1))
+        return lcs(a.substring(0,aLen-1),b.substring(0,bLen-1))
-            + a.charAt(a.length()-1);
+            + a.charAt(aLen-1);
     }else{
-        String x = lcs(a, b.substring(0,b.length()-1));
+        String x = lcs(a, b.substring(0,bLen-1));
-        String y = lcs(a.substring(0,a.length()-1), b);
+        String y = lcs(a.substring(0,aLen-1), b);
         return (x.length() > y.length()) ? x : y;
     }