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"
Code language: PHP (php)

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); } }
Code language: Java (java)

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; } }
Code language: Java (java)

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! } }
Code language: Java (java)

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")); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments