1143. 가장 긴 공통 부분 수열(자바스크립트 솔루션)

설명:

두 개의 문자열 text1과 text2가 주어지면 가장 긴 공통 부분 시퀀스의 길이를 반환합니다. 공통 부분 수열이 없으면 0을 반환합니다.

문자열의 하위 시퀀스는 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자(없을 수 있음)가 삭제된 원래 문자열에서 생성된 새 문자열입니다.

예를 들어 "ace"는 "abcde"의 하위 시퀀스입니다.
두 문자열의 공통 하위 시퀀스는 두 문자열에 공통인 하위 시퀀스입니다.

해결책:

시간 복잡도 : O(n^2)
공간 복잡도: O(n^2)

var longestCommonSubsequence = function(text1, text2) {
    // Create dp table
    const dp = Array(text1.length+1).fill(0).map(() => Array(text2.length+1).fill(0))
    for(let i = 1; i < dp.length; i++) {
        for(let j = 1; j < dp[i].length; j++) {
            // If the letters match, look diagonally to get the max subsequence before this letter and add one
            if(text1[i-1]===text2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                // If there is no match, set the cell to the previous current longest subsequence
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
            }
        }
    }
    return dp[text1.length][text2.length]
};