[Leetcode] *72. Edit Distance

문제

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a characterDelete a characterReplace a character
 
Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
 
Constraints:
0 <= word1.length, word2.length <= 500word1 and word2 consist of lowercase English letters.

 

풀이

dp[i][j] = distance between word1[i] and word[j] 를 의미한다.

when j=0 (word2 = ""), dp[i][0] = i,

when i=0 (word1 = ""), dp[0][j] = j,

그 외에, when word1[i] == word2[j], dp[i][j] = dp[i-1][j-1] 이 된다. (min edit dist)

 when word1[i] != word2[j], 왼쪽, 왼쪽 위, 위쪽 중 가장 작은 dist 에 1을 더한 값이 된다.

 

자세한 이유는 링크를 참조..

https://m.blog.naver.com/ndb796/220870218783

최소 편집 거리(Minimum Edit Distance) 알고리즘

 

코드

#define min(a,b) ((a) < (b) ? (a) : (b))

int minDistance(char* word1, char* word2) {
    int size1 = strlen(word1);
    int size2 = strlen(word2);

    int dp[size1+1][size2+1]; // distance array
    memset(dp, 0, sizeof(dp));

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