[LeetCode] 1143. Longest Common Subsequence, Medium

1. 문제

• 문자열 text1과 text2가 주어질 때, 순서는 유지하면서 연속되지 않아도 되는 가장 긴 공통 부분 문자열의 길이를 구하라.

2. 해결

function longestCommonSubsequence(text1: string, text2: string): number {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

• 어찌 저찌 풀려고 해봤는데, 안됐다.
• 이 문제는 LCS 문제로 탐색중인 두 문자가 동일하면, i-1, j-1의 LCS 값 +1을 해주고 다르면 해당 문자 혹은 비교 문자를 포함하지 않은 LCS 값 중 최대 값을 최하면 된다.