[LeetCode] Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=leetcode-75

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.
 

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

---

순서를 고려해서 주어진 두 개의 문자열에 공통으로 들어가는 문자열의 최대 길이를 구하는 문제!

순서를 바꾸지 않고 중간에 문자를 제거해도 된다.

DP는 뭔가 어떻게 하는지 알 것 같으면서도 막상 코드로 구현하려면 감이 안 잡힌다 ?_?

 

- Try dynamic programming. DP[i][j] represents
the longest common subsequence of text1[0 ... i] & text2[0 ... j].
- DP[i][j] = DP[i - 1][j - 1] + 1 ,
if text1[i] == text2[j] DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) , otherwise

 

어쩔 수 없이 힌트를 보고...

 

 

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

    for (let i = 1; i <= length1; i++) {
        for (let j = 1; j <= length2; 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[length1][length2];
};

 

우선 결과를 저장할 dp 배열을 만든다.

이차 배열로, dp[i][j] 는 text1의 i번째와 text2의 j번째까지 비교했을 때 가장 긴 공통 부분의 문자열의 길이를 나타낸다.

 

처음에는 아래처럼 배열을 만들었는데,

const dp = new Array(m + 1).fill(new Array(n + 1).fill(0));

 

이렇게 만들면 안 된다. 이렇게 하면 모든 행이 같은 배열을 공유하게 된다.

dp[0], dp[1], ... dp[m] 모두가 같은 배열을 가리키는 참조값을 복사받는 것이다.

 

const row = new Array(2).fill(0);
const dp = new Array(3).fill(row);

이렇게 하는 거랑 똑같다.

 

저렇게 만들면 이런 식으로 값을 변경했을 때 dp[1][1]만 변경되는 게 아니라 dp[x][1]의 모든 자리가 변경된다.

그러니까... Array.from을 사용하면 각 독립된 배열 객체로 만들 수 있게 된다.

const dp = Array.from({ length: length1 + 1 }, () => Array(length2 + 1).fill(0));

 

그리고 for문을 이중으로 돌면서 text1[i-1]과 text2[j-1]이 같을 때 이전까지의 결과에 1을 더한다. 

문자가 다른 경우에는 text1의 i-1까지 비교한 결과와 text2의 j-1까지 비교한 결과 중 더 긴 것을 보관한다.

 

text1 = "abcde", text2 = "ace" 를 예시로 들면 배열은 아래처럼 나타난다.

      a  c  e   ← text2 (열)
   0  0  0  0
a  0  1  1  1
b  0  1  1  1
c  0  1  2  2
d  0  1  2  2
e  0  1  2  3
↑
text1 (행)

 

 

이런 식으로 힘들게 푼 문제는 나중에 꼭 다시 풀어야 할 것 같다....