längste gemeinsame Teilfolge java (rekursiv)

Question

Das Problem, das ich auf mich arbeiten, ist hier: http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

im Grunde sind wir zwei Strings gegeben und wir sind die längste gemeinsame Teilfolge zu finden angefordert. Ich habe online nach Lösungen gesucht und diese mit meiner eigenen Lösung verglichen. In meinem Code konnte ich keine Fehler finden. Ich frage mich, warum es immer noch nicht funktioniert.

Und auch, wurde ich gebeten, dieses Problem zu lösen, indem rekursive Methoden

Hier ist mein Code:

public static String longestCommonSubsequence(String a, String b){ 
    if(a.isEmpty() || b.isEmpty()){ 
        return ""; 
    } 
    if (a.substring(a.length() - 1).equals(b.substring(b.length() - 1))){ 
        return longestCommonSubsequence(a.substring(0, a.length() - 1), b.substring(0, b.length() 
         - 1)) + a.substring(a.length() - 1); 
    } else { 
        String first = longestCommonSubsequence(a, b.substring(b.length() - 1)); 
        String second = longestCommonSubsequence(a.substring(a.length() - 1), b); 
        if(first.length() > second.length()){ 
            return first; 
        } 
        return second; 
    } 
} 

Und hier sind die alle Testfälle:

Anruf Rückgabewert

"ABCDEFG", "BGCEHAF" "BCEF"

"sie verkauft", "Muscheln" "sesells"

"12345", "54321 21 54321" "123"

"supercilious Lehrer", "köstlich Pfirsich" "ecious jedes"

" Marty“, "Helene" ""

"", "Joe" ""

"Suzy", "" ""

"ACGGTGTCGTGCTA", "CGTTCGGCTATCGTACGT" "CGGTTCGTGT"

mit meinem Code habe ich StackOverFlow für alle Testfälle.

Answer 1

Ihre LCS-Berechnung ist nicht korrekt. In LCS müssen Sie vom Ende des Strings vergleichen. Wenn die letzten Zeichen von zwei Strings übereinstimmen, bedeutet dies, dass es Teil Ihres LCS wäre.

public static String longestCommonSubsequence(String a, String b) { 
     int alength = a.length() - 1; 
     int blength = b.length() - 1; 

     if (alength < 0 || blength < 0) 
      return ""; 

     if (a.substring(alength).equals(b.substring(blength))) { 
      return longestCommonSubsequence(a.substring(0, alength), b.substring(0, blength)) 
        + a.substring(alength); 
     } else { 
      String first = longestCommonSubsequence(a, b.substring(0, blength)); 
      String second = longestCommonSubsequence(a.substring(0, alength), b); 
      if (first.length() > second.length()) { 
       return first; 
      } else { 
       return second; 
      } 
     } 
    }