[C++] 편집 거리 알고리즘(Edit Distance Algorithm)

편집 거리 알고리즘

1. 개념

편집 거리 알고리즘(Edit Distance Algorithm)은 두 개의 문자열 A, B가 주어졌을 때, 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘이다. 즉, 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산을 진행해야 하는지 알 수 있다. 여기서의 연산이란 삽입(Insertion), 삽입(Deletion), 대체(Replacement)를 말한다.

 

문자열 간의 유사도 측정처럼 기본적으로는 두 데이터 사이의 유사도를 알아내기 위해 사용할 수 있으며 특히 프로그램의 표절 여부, 철자 오류 검사 등에 사용할 수 있다.

 

철자 오류

 

2. 기본 원리

 

3. 문제

https://leetcode.com/problems/edit-distance/description/

Edit Distance - LeetCode

#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int dp[502][502]{};

    int minDistance(string word1, string word2) {
        for (int i = 0; i < word1.size(); i++)
            dp[i + 1][0] = i + 1;
        for (int j = 0; j < word2.size(); j++)
            dp[0][j + 1] = j + 1;

        for (int i = 1; i <= word1.size(); i++)
        {
            for (int j = 1; j <= word2.size(); j++)
            {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

 

참고

https://madplay.github.io/post/levenshtein-distance-edit-distance

편집거리 알고리즘 Levenshtein Distance(Edit Distance Algorithm)

https://velog.io/@rivolt0421/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Edit-distance

🎲[알고리즘] Edit distance