[DP - Multidimensional, Medium] Edit Distance

https://leetcode.com/problems/edit-distance/?envType=study-plan-v2&envId=leetcode-75

2차원 dp 배열을 사용한다.
word1의 i번째와 word2의 j번째 수행 결과는 dp[i + 1][j + 1]에 들어갈 것이므로
dp배열의 크기는 [word1.length() + 1][word2.length() + 1]로 해준다.

dp배열 초기화는 dp[i][0] = i, dp[0][j] = j 각각 수행해준다.
왜냐하면 최악의 경우 모든 연산이 삽입이 되어야 하기 때문이다.
(매 글자마다 삽입했을 때의 오퍼레이션 수)

이후 2중 for문을 돌면서 word1, word2의 캐릭터끼리 비교한다.

• word1.charAt(i - 1) == word2.charAt(j - 1) -> 같은 글자에서 온 경우, 별도의 오퍼레이션이 필요없음
  • dp[i][j] = dp[i - 1][j - 1];
• 다른 글자에서 온 경우, 아래 세 가지 오퍼레이션 중 가장 작은 값
  • replace: dp[i - 1][j - 1] + 1
  • delete: dp[i - 1][j] + 1
  • insert: dp[i][j - 1] + 1

항상 정해진 방향 (word1 으로 word2를 만드는 것)이므로 i - 1, j - 1에 따라 delete/insert를 구분할 수 있다.

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        int[][] dp = new int[n + 1][m + 1];

        for (int i=0; i<=n; i++) {
            dp[i][0] = i;
        }
        for (int j=0; j<=m; j++) {
            dp[0][j] = j;
        }

        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {

                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];
                    int delete = dp[i - 1][j];
                    int insert = dp[i][j - 1];

                    dp[i][j] = Math.min(replace, Math.min(delete, insert)) + 1;
                }
            }
        }

        return dp[n][m];
    }
}