1143. Longest Common Subsequence (TypeScript)

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.

 

 

 

function longestCommonSubsequence(text1: string, text2: string): number {
 //step1
  const rowLen = text1.length + 1;
  const colLen = text2.length + 1;
  const dp = Array.from({ length: rowLen },() => Array(colLen).fill(0)) ;

  //step2
  for (let x = 1; x < rowLen; x++) {
    for (let y = 1; y < colLen; y++) {
      if (text1[x - 1] === text2[y - 1]) { //a==a
        dp[x][y] = dp[x - 1][y - 1] + 1; //prevDiagnolIndex
      } else {
        dp[x][y] = Math.max(dp[x - 1][y], dp[x][y - 1]);
      }
    }
  }

  return dp[rowLen - 1][colLen - 1];
}

 

 

1. rowLen과 colLen을 계산하여 각 문자열의 길이에 1을 더한 값을 저장. 이는 문자열의 길이를 저장하는 변수
2. dp 배열을 생성하여 두 문자열의 길이에 1을 더한 크기로 초기화. 이 배열은 동적 프로그래밍에서 중간 결과를 저장하는 데 사용
3. 중첩된 반복문을 사용하여 두 문자열을 비교하며 가장 긴 공통 부분 수열의 길이를 계산.
4. 만약 현재 문자가 같다면(text1[x - 1] === text2[y - 1]), 이전 대각선의 값에서 1을 더한 값을 현재 위치에 저장. 이는 이전 문자열까지의 가장 긴 공통 부분 수열의 길이에 현재 문자를 추가한 값
5. 문자가 다르다면, 현재 위치의 값은 이전 행의 값과 이전 열의 값 중 큰 값으로 설정 이는 현재 문자를 무시하고 이전 문자열까지의 가장 긴 공통 부분 수열의 길이를 가져오는 것
6. 반복문을 마치고, dp[rowLen - 1][colLen - 1]에는 두 문자열의 가장 긴 공통 부분 수열의 길이가 저장되어 있음. 이 값을 반환