Longest Common Sequence

LongestCommonSequence.java

public class LongestCommonSequence {
	public static void main(String[] args) {
		String str1 = "ABCBDAB";
		String str2 = "BDCABA";
		String lcs = lcs(str1, str2);

		System.out.println(lcs);
		System.out.println(lcs.length());
	}

	private static String lcs(String input1, String input2) {
		if (input1 == null || input2 == null) {
			return "";
		}

		int len1 = input1.length();
		int len2 = input2.length();
		int[][] lenMatrix = new int[len1 + 1][len2 + 1];
		int[][] dirMatrix = new int[len1 + 1][len2 + 1];

		for (int row = 1; row <= len1; row++) {
			for (int col = 1; col <= len2; col++) {
				if (input1.charAt(row - 1) == input2.charAt(col - 1)) {
					lenMatrix[row][col] = lenMatrix[row - 1][col - 1] + 1;
					dirMatrix[row][col] = 1;
				} else {
					if (lenMatrix[row - 1][col] >= lenMatrix[row][col - 1]) {
						lenMatrix[row][col] = lenMatrix[row - 1][col];
						dirMatrix[row][col] = 2;

					} else {
						lenMatrix[row][col] = lenMatrix[row][col - 1];
						dirMatrix[row][col] = 3;
					}
				}
			}
		}

		StringBuilder result = new StringBuilder();

		int row = len1;
		int col = len2;
		while (row > 0 && col > 0) {
			if (dirMatrix[row][col] == 1) {
				char ch = input1.charAt(row - 1);
				result.insert(0, ch);
				row--;
				col--;
			} else if (dirMatrix[row][col] == 2) {
				row--;
			} else if (dirMatrix[row][col] == 3) {
				col--;
			}
		}

		return result.toString();
	}
}