LeetCode : 72. Edit Distance

LCS와 매우 유사한 유형이다.. LCS와 Edit Distance모두 2차원 DP를 이용한다? 그리고 전체적인 로직 부분이 매우 유사합니다.

다만! LCS는 공통된 부분을 찾으면 +1을 해나가는 로직이지만,

Edit Distance는 공통된 부분을 찾으면 그냥 놔두고 공통되지 않은 부분이 나오면 오히려 insert, delete, replace작업을 해주어야 하기 때문에 +1만큼 더해준다.

 

사실 처음에는 어떻게 풀지 감이 오지 않아서...ㅎㅎ

유투브를 참고해서 풀었다.

www.youtube.com/watch?v=b6AGUjqIPsA&feature=youtu.be

 

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        int dp[502][502] = {0, };
        
        for(int i=1; i<=n; i++){
            dp[i][0] = i;
        }
        
        for(int j=1; j<=m; j++){
            dp[0][j] = j;
        }
        
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{ // insert, delete, replace
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }
        
        return dp[n][m];
    }
};