문제 개요

문제: 공통 부분 문자열

분류: DP, 문자열

난이도: 골드5

문제 풀이

DP를 통해 풀이했다.

첫 번째 문자열의 문자를 참조하는 인덱스 a,
두 번째 문자열의 문자를 참조하는 인덱스 b가 있다고 하자.

두 문자열을 앞에서부터 비교하며 현재 각 문자열의 문자가 같은 경우에만 dp[a][b]를 dp[a-1][b-1]+1로 갱신한다.
이 과정에서 가장 큰 값을 정답 변수에 저장한다.

예를 들어 “ABRAC”와 “EABBRA”의 두 문자열이 주어졌을 때 dp 배열은 아래와 같이 채워지며, 정답은 3이 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [str1, str2] = fs.readFileSync(filePath).toString().trim().split("\n");

const solution = (str1, str2) => {
  const dp = Array.from({ length: str1.length + 1 }, () =>
    new Array(str2.length + 1).fill(0)
  );
  let answer = 0;

  for (let i = 1; i <= str1.length; i++) {
    for (let j = 1; j <= str2.length; j++) {
      if (str1[i - 1] === str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      answer = Math.max(answer, dp[i][j]);
    }
  }

  console.log(answer);
};

solution(str1, str2);