Longest common Subsequence

ghz 10months ago ⋅ 67 views

The Longest Common Subsequence (LCS) problem is a classic dynamic programming problem. Given two sequences, the task is to find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

Here's a Java implementation of LCS using dynamic programming:

public class LongestCommonSubsequence {
    
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // Create a DP array to store the lengths of the longest common subsequences
        int[][] dp = new int[m+1][n+1];
        
        // Fill the DP array
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    // If characters match, take diagonal + 1
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // If characters don't match, take max of left and top
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        // The length of the LCS is at the bottom-right corner of the DP array
        return dp[m][n];
    }

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("Length of Longest Common Subsequence: " + longestCommonSubsequence(text1, text2)); // Output: 3
    }
}

In this implementation:

  • We create a 2D DP array dp of size (m+1) x (n+1), where m and n are the lengths of the input strings text1 and text2 respectively.
  • We iterate through the strings and fill the DP array based on the lengths of the longest common subsequences.
  • If the characters at the current positions match, we take the value from the diagonal element and increment it by 1.
  • If the characters don't match, we take the maximum of the element to the left and the element above.
  • The length of the longest common subsequence is at the bottom-right corner of the DP array, which is returned as the result.
#algorithm