LeetCode 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 character
• Delete a character
• Replace a character

---

코드

class Solution {
    public int minDistance(String word1, String word2) {
        //dp 배열 초기화
        int[][] dp=new int[word1.length()+1][word2.length()+1];
        
        //공집합에서 word2를 만들 때의 edit distance, word1을 만들 때의 edit distance를 memoization
        for(int i=0; i<=word1.length(); i++)
            dp[i][0]=i;
        for(int i=0; i<=word2.length(); i++)
            dp[0][i]=i;
        
        for(int i=1; i<=word1.length(); i++){
            for(int j=1; j<=word2.length(); j++){
                //현재의 문자가 같다면, 
                //word1, word2 각각 현재 문자 이전까지의 edit distance에 그대로 붙이면 됨
                if(word1.charAt(i-1)==word2.charAt(j-1))
                    dp[i][j]=dp[i-1][j-1];
                //현재의 문자가 다르다면
                else{
                    int replace=dp[i-1][j-1]+1;
                    int delete=dp[i-1][j]+1;
                    int insert=dp[i][j-1]+1;
                    dp[i][j]=Math.min(replace, Math.min(delete, insert));
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}

---

해결 과정

1. LCS(Longest Common Subsequence) 알고리즘으로 어떻게 해보려다가 결국 혼자 풀지 못했다. 두 문자의 유사도를 알 수 있는 편집 거리 알고리즘을 사용해서 해결할 수 있다.

2. 😁