[리트코드] 1143. Longest Common Subsequence - js (DP)

1. 문제

https://leetcode.com/problems/longest-common-subsequence/

Longest Common Subsequence - LeetCode

2. 코드

이 문제는 DP(누적합)를 이용하여 푼다.

text1 : ace
text2 : abcde

text1 길이  + 1 만큼의 요소를 가지고 있고, 각 개별 요소 길이가 text2 길이 + 1 인 배열을 만든다. 순서가 바뀌어도 상관 없다. 첫 번째 열과 행은 계산을 위해 존재하는 행이라고 생각하면 편하다. 없는 셈 쳐도 된다. 그 곳에 값을 넣을 게 아니기 때문에.

그리고 비교 기준을 text2, 비교 대상을 text1로 잡는다.

배열의 각 자리의 값은 text1의 0 ~ j 과 text2의 0 ~ i 에서 겹치는 단어 누적 개수의 최대값이 된다.

    - a b c d e
 -  0 0 0 0 0 0
 a  0 1 1 1 1 1
 c  0 1 1 2 2 2
 e  0 1 1 2 2 3

예를 들어 ace의 c, abcd의 d를 비교할 때, 요소의 값이 될 수 있는 숫자는

• 1(a,abcd 비교 = dp[i][j+1])
• 2(ac,abc 비교 = dp[i+1][j])

가 된다. 둘 중 더 큰 값은 2 이므로 요소의 값은 2가 된다.

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let dp = Array.from({length : text1.length + 1}).map(() => Array(text2.length + 1).fill(0));

    for (let i=0;i<text1.length; i++) {
        for (let j=0;j<text2.length; j++)
            dp[i+1][j+1] = text1[i] === text2[j] ? dp[i][j]+1 : Math.max(dp[i][j+1],dp[i+1][j]);
    }

    return dp[text1.length][text2.length];
};

 

하나 하나 천천히 짚어가니 코드의 짜임새가 이해 된다.. DP는 단연코 내가 접해봤던 문제 중 가장 문제를 보고 떠오르지 않는 유형 1위인 것 같다.