← 20주차 · DP 심화 (2차원)
보통DP문자열

최장 공통 부분 수열

두 문자열 a와 b가 주어져요. 두 문자열 모두에서 순서를 지켜 뽑을 수 있는 공통 부분 수열 중 가장 긴 것의 길이를 반환해요. 글자가 이어져 있을 필요는 없어요.

두 문자열을 나란히 놓고 표를 채워요. dp[i][j]를 'a의 앞 i글자와 b의 앞 j글자의 최장 공통 부분 수열 길이'라 하면, 마지막 글자가 같으면 dp[i-1][j-1] + 1, 다르면 dp[i-1][j]와 dp[i][j-1] 중 큰 값이에요.

예시

예시 1
입력
a = "abcde", b = "ace"
출력
3
설명
"ace"가 두 문자열에 순서대로 들어 있어요.
예시 2
입력
a = "abc", b = "abc"
출력
3
예시 3
입력
a = "abc", b = "def"
출력
0

제한 사항

  • 0 ≤ a.length, b.length ≤ 1,000
  • 두 문자열은 소문자 알파벳으로 이루어져요.
(a.length + 1) × (b.length + 1) 크기의 표를 0으로 채워요. i, j를 1부터 돌며 a[i-1] === b[j-1]이면 dp[i][j] = dp[i-1][j-1] + 1, 아니면 Math.max(dp[i-1][j], dp[i][j-1])로 채워요. 오른쪽 아래 칸이 답이에요.
javascript
function lcsLength(a, b) {
  const m = a.length;
  const n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[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[m][n];
}
이전 문제0-1 배낭
다음 문제편집 거리
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.