문자열 - 레벤슈타인 거리

레벤슈타인 거리

두 문자열이 있을 때, 한 문자열을 다른 문자열로 변환할 때 필요한 최소한의 작업(추가, 삭제, 치환) 횟수

• 추가 : m -> me
• 삭제 : me -> m
• 치환 : me -> my

두 문자열을 각각 행, 열로 가지는 행렬을 생성하고, 그 위치에서 한 문자열을 다른 문자열로 변환할 때 필요한 작업 횟수를 계산한다.

const LevenshteinDistance = (str1, str2) => {
  const matrix = Array(str2.length + 1)
    .fill(null)
    .map(() => Array(str1.length + 1).fill(null));

  for (let i = 0; i <= str1.length; i++) {
    matrix[0][i] = i;
  }

  for (let j = 0; j <= str2.length; j++) {
    matrix[j][0] = j;
  }

  for (let j = 1; j <= str2.length; j++) {
    for (let i = 1; i <= str1.length; i++) {
      const isIdentical = str1[i - 1] === str2[j - 1] ? 0 : 1; // 직전 위치의 문자 일치 여부
      matrix[j][i] = Math.min(
        matrix[j][i - 1] + 1, // 문자 삭제
        matrix[j - 1][i] + 1, // 문자 추가
        matrix[j - 1][i - 1] + isIdentical // 문자 치환
      );
    }
  }

  return matrix[str2.length][str1.length];
};