In this course, we will discuss the problem of “Longest Common Subsequence (LCS)”, which is frequently encountered in coding tests. The LCS problem involves finding the longest common subsequence that can be formed by preserving the relative order of elements in both sequences when given two sequences.<\/p>\n
Given two strings Length of the longest common subsequence : 4<\/p>\n To solve this problem, we will use the dynamic programming approach. Dynamic programming is a method for solving problems by breaking them down into smaller subproblems and storing the results to efficiently solve the problem.<\/p>\n Create a two-dimensional array Each element of the array is initialized to 0.<\/p>\n<\/div>\n Now we will fill the two-dimensional array Ultimately, the value of Now let’s implement this process in Java code.<\/p>\n The code above operates in the following manner.<\/p>\nstr1<\/code> and str2<\/code>, find the length of the longest common subsequence of these two strings.<\/p>\nInput<\/h3>\n
\n
str1<\/code> : “AGGTAB”<\/li>\nstr2<\/code> : “GXTXAYB”<\/li>\n<\/ul>\nOutput<\/h3>\n
Problem Solving Process<\/h2>\n
Step 1: Initialize the Two-Dimensional Array<\/h3>\n
dp<\/code> based on the lengths of strings str1<\/code> and str2<\/code>. The size of this array is (m+1) x (n+1)<\/code>, where<\/p>\n\n
m<\/code> : length of str1<\/code><\/li>\nn<\/code> : length of str2<\/code><\/li>\n<\/ul>\nStep 2: Fill the Two-Dimensional Array<\/h3>\n
dp<\/code>. We will proceed by comparing each character of the strings.<\/p>\n\n
dp[i][j] = dp[i-1][j-1] + 1<\/code>.<\/li>\ndp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])<\/code>.<\/li>\n<\/ol>\ndp[m][n]<\/code> will be the length of the longest common subsequence.<\/p>\n<\/div>\nStep 3: Implement the Code<\/h3>\n
\npublic class LongestCommonSubsequence {\n public static int lcs(String str1, String str2) {\n int m = str1.length();\n int n = str2.length();\n int[][] dp = new int[m + 1][n + 1];\n\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (str1.charAt(i - 1) == str2.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n } else {\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n\n return dp[m][n];\n }\n\n public static void main(String[] args) {\n String str1 = \"AGGTAB\";\n String str2 = \"GXTXAYB\";\n System.out.println(\"Length of the longest common subsequence: \" + lcs(str1, str2));\n }\n}\n <\/code><\/pre>\nCode Analysis<\/h2>\n
\n
dp<\/code> array based on their lengths.<\/li>\nExecution Result<\/h2>\n