[PS] Leet | 1143. 가장 긴 공통 배열

문제

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

예시

Example 1:
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

조건

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

답

DP를 이용합니다.

 

text1의 길이를 i, text2의 길이를 j라고 했을 때, 가장 긴 공통 배열의 길이를 [i, j]라고 합시다.

 

만약 각 문자열에서 한 자 만큼이 추가되었을 때, 그 두 문자가 같다면 그 둘을 짝 지어서 [i+1, j+1] = [i, j] + 1이 됩니다.

 

(공통 배열의 종류가 아닌, 길이를 구하는 것이기 때문에 무조건 이 둘을 짝지어도 문제되지 않습니다)

 

두 문자가 같지 않다면, [i+1, j+1] = max{ [i, j-1], [i-1, j] } 로 계산합니다.

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    const len1 = text1.length;
    const len2 = text2.length;

    const lst = [];
    let prev = [];

    for (let i=0; i<len2+1; ++i){
        lst.push(0);
        prev.push(0);
    }

    for (let i=1; i<=len1; ++i) {
        for (let j=1; j<=len2; ++j) {
            if (text1[i-1] === text2[j-1]) {
                lst[j] = prev[j-1] + 1; 
            } else {
                lst[j] = Math.max(prev[j], lst[j-1]);
            }
        }
        prev = [...lst];
    }

    return lst[text2.length];
};

text1의 길이를 n, text2의 길이를 m이라 할 때

시간 복잡도 : O(nm)

공간 복잡도 : O(m)