[leetCode/JS] 1143. Longest Common Subsequence

난이도 [ 🤔 ] Medium

 

문제 설명

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로 풀어야한다는 것까지 생각했지만
• 점화식이나 아이디어가 떠올르지 않아서 구글링함..ㅠ_ㅠ
• 자세한 설명은 여기서 https://sumim.tistory.com/entry/LeetCode-1143-Longest-Common-Subsequence 구경하세요

var longestCommonSubsequence = function(text1, text2) {
  let matrix = Array(text1.length + 1).fill(0).map(x => Array(text2.length + 1).fill(0))
  for(let i = 1; i < matrix.length; i++){
    for(let j = 1; j < matrix[0].length; j++){
      if(text1[i-1] === text2[j-1]){
        matrix[i][j] = matrix[i-1][j-1] + 1;
      } else {
        matrix[i][j] = Math.max(matrix[i-1][j], matrix[i][j-1]);
      }
    }
  }
  return matrix[text1.length][text2.length];
};

 

감상평

• DP는 개념이긴한데, 2차원 배열을 만들어서 이전과 비교하는 방식은 처음이네!
• 어려운 문제는 참 많구만 어렵다 어려워
• 빠르긴 겁나 빠르네.