{"id":34566,"date":"2024-11-01T09:29:30","date_gmt":"2024-11-01T09:29:30","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34566"},"modified":"2024-11-01T11:40:41","modified_gmt":"2024-11-01T11:40:41","slug":"javascript-coding-test-course-longest-common-subsequence","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34566\/","title":{"rendered":"JavaScript Coding Test Course, Longest Common Subsequence"},"content":{"rendered":"

<\/p>\n

\n

Problem Description<\/h2>\n

\n Given two strings, the problem is to find the Longest Common Subsequence (LCS) of these two strings.
\n The longest common subsequence refers to the maximum length of the substring that overlaps while maintaining the order of the two strings.
\n For example, if string A is “ABCBDAB” and string B is “BDCAB”, the longest common subsequence can be “BDAB” or “BCAB”, etc.\n <\/p>\n

Input Format<\/h2>\n

\n – The first line contains the length N of string A and the length M of string B. (1 \u2264 N, M \u2264 1000)
\n – The second line contains string A.
\n – The third line contains string B.\n <\/p>\n

Output Format<\/h2>\n

\n – Output the length of the longest common subsequence of the two strings.\n <\/p>\n

Example<\/h2>\n
\n            Input:\n            7 5\n            ABCBDAB\n            BDCAB\n\n            Output:\n            4\n        <\/pre>\n
Approach to Solve the Problem<\/h2>\n
\n            This problem is a typical example of Dynamic Programming.
\n            To find the LCS, we compare the two strings to find matching characters,
\n            solving the subproblems at that point to derive the final length.\n        <\/p>\n
Step-by-Step Approach<\/h3>\n
    \n
  1. \nInitialize the Dynamic Programming Table:<\/strong><\/p>\n
    \n                    Create a 2D array DP. DP[i][j] stores the length of the longest common subsequence
    \n                    of the first i characters of string A and the first j characters of string B. The size of the array is (N+1) x (M+1).\n                <\/p>\n<\/li>\n
  2. \nFill the Table:<\/strong><\/p>\n
    \n                    If the i-th character of A and the j-th character of B are the same, then DP[i][j] = DP[i-1][j-1] + 1.
    \n                    Otherwise, set DP[i][j] = max(DP[i-1][j], DP[i][j-1]).\n                <\/p>\n<\/li>\n
  3. \nOutput the Result:<\/strong><\/p>\n
    \n                    By reaching DP[N][M], we can return the length of the longest common subsequence.\n                <\/p>\n<\/li>\n<\/ol>\n
    JavaScript Code<\/h2>\n
    \nfunction longestCommonSubsequence(A, B) {\n    const N = A.length;\n    const M = B.length;\n    \n    \/\/ Initialize the DP table\n    const DP = Array.from(Array(N + 1), () => Array(M + 1).fill(0));\n    \n    \/\/ Fill the DP table\n    for (let i = 1; i <= N; i++) {\n        for (let j = 1; j <= M; j++) {\n            if (A[i - 1] === B[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[N][M];\n}\n\n\/\/ Run the input example\nconst A = 'ABCBDAB';\nconst B = 'BDCAB';\nconsole.log(longestCommonSubsequence(A, B)); \/\/ Output: 4\n        <\/code><\/pre>\n
    Review and Practice Problems<\/h2>\n
    \n            If you have fully understood this problem, try to enhance your skills with additional practice problems. Challenge yourself with the following problems:\n        <\/p>\n