Print for Longest common subsequence-CodePudding

longestCommonSubsequence is returning the length of LCS. The code works fine. But I am trying to print the value of Subsequence .For below example it should print "acef" .But my code is printing only "ae".
How to fix it?

Here is the complete code https://pastebin.com/Sq4QMtxF

//Code to print the LCS
        int x = a.length();
        int y = b.length();

        String s = "";

        while (x > 0 && y > 0) {
            if (a.charAt(x - 1) == b.charAt(y - 1)) {
                s = a.charAt(x - 1)   s;
                x--;
                y--;
            } else {
                if (memo[x - 1][y] > memo[x][y - 1])
                    x--;
                else
                    y--;
            }
        }
        System.out.println(s);

CodePudding user response：

Your code to get LCS uses a top down approach and your memo is built from 0,0 and so your answer is at memo[0][0].

In order to get the LCS string from memo you need to traverse from top to bottom. Also use StringBuilder instead of adding it to a String ( it will create a new object every time you add to a String ). With that the change will be:

int x = 0, y = 0;
StringBuilder sb = new StringBuilder();
while (x < a.length() && y < b.length()) {
    if (a.charAt(x) == b.charAt(y)) {
        sb.append(a.charAt(x));
        x  ;
        y  ;
    } else {
        if (memo[x   1][y] > memo[x][y   1])
            x  ;
        else
            y  ;
    } 
            
}
System.out.println(sb.toString());