Find the Longest Common Subsequence in Java

The challenge

from Wikipedia:
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences.
It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Task

Write a function lcs that accepts two strings and returns their longest common subsequence as a string. Performance matters.

Examples

lcs( "abcdef", "abc" ) => "abc"
lcs( "abcdef", "acf" ) => "acf"
lcs( "132535365", "123456789" ) => "12356"
lcs( "abcdefghijklmnopq", "apcdefghijklmnobq" ) => "acdefghijklmnoq"

Notes

The subsequences of "abc" are "", "a", "b", "c", "ab", "ac", "bc", "abc".
"" is a valid subsequence in this challenge, and a possible return value.
All inputs will be valid.
Two strings may have more than one longest common subsequence. When this occurs, return any of them.

lcs( string0, string1 ) === lcs( string1, string0 )

The solution in Java code

Option 1:

class Lcs {

  static String lcs(String a, String b) {
    return backtrack(buildDistanceArray(a, b), a, b, a.length(), b.length());
  }
  
  private static int[][] buildDistanceArray(String s1, String s2){
    int[][] returnArray = new int[s1.length() + 1][s2.length() + 1];
    for(int i = 1; i <= s1.length(); i++){
      for (int j = 1; j <= s2.length(); j++){
        returnArray[i][j] = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 
                            returnArray[i-1][j-1] + 1: 
                            Math.max(returnArray[i][j-1], returnArray[i-1][j]);
      }
    }
    return returnArray;
  }
  
  private static String backtrack(int[][] distArray, String s1, String s2, int i, int j){
    if(i * j == 0) return "";
    if(s1.charAt(i - 1) == s2.charAt(j - 1)) return backtrack(distArray, s1, s2, i-1, j-1) + s1.charAt(i - 1);
    if (distArray[i][j-1] > distArray[i-1][j]) return backtrack(distArray, s1, s2, i, j-1);
    return backtrack(distArray, s1, s2, i-1, j);
  }
}

Option 2:

class Lcs {
public static String lcs(String x, String y) {

    if (x.length() == 0 || y.length() == 0 || x == null || y == null)
        return "";

    String MaxResult = "";
    String result = "";
    for (int i = 0; i < x.length(); i++) {

        String currRes = x.substring(i, i+1);
        int posRes = y.indexOf(currRes);
        if (posRes >= 0) {
          result = currRes+lcs(x.substring(i+1),y.substring(posRes+1));
        }
        if (result.length() > MaxResult.length()) {MaxResult = result;}
      }

      return MaxResult;
  }
}

Option 3:

class Lcs {

  static String lcs(String a, String b) {
    int[][] matrix = new int[a.length() + 1][b.length() + 1];
    for(int i=1; i <= a.length(); i++){
      for(int j=1; j <= b.length(); j++){
        if(a.charAt(i-1) == b.charAt(j-1)){
          matrix[i][j] = matrix[i-1][j-1] + 1;
        }else{
          matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1]);
        }
      }
    }
    
    StringBuilder seq = new StringBuilder();
    int i, j;
    i = a.length();
    j = b.length();
    while(i > 0 && j > 0){
        if(a.charAt(i-1) == b.charAt(j-1)){
          seq.append(b.charAt(j-1));
          i--;
          j--;
        }else{
          if(matrix[i-1][j] > matrix[i][j-1]){
            i--;
          }else
            j--;
        }
      }
    String out = seq.reverse().toString();
    return out; // do it!
  }
}

Test cases to validate our solution

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

import static org.junit.Assert.assertEquals;

public class LcsTest {
	@Test
	public void fixedTests() {
		assertEquals("", Lcs.lcs("", ""));
		assertEquals("", Lcs.lcs("abc", ""));
		assertEquals("", Lcs.lcs("", "abc"));
		assertEquals("", Lcs.lcs("a", "b"));
		assertEquals("a", Lcs.lcs("a", "a"));
		assertEquals("ac", Lcs.lcs("abc", "ac"));
		assertEquals("abc", Lcs.lcs("abcdef", "abc"));
		assertEquals("acf", Lcs.lcs("abcdef", "acf"));
		assertEquals("nottest", Lcs.lcs("anothertest", "notatest"));
		assertEquals("12356", Lcs.lcs("132535365", "123456789"));
		assertEquals("final", Lcs.lcs("nothardlythefinaltest", "zzzfinallyzzz"));
		assertEquals("acdefghijklmnoq", Lcs.lcs("abcdefghijklmnopq", "apcdefghijklmnobq"));
	}
}