# Leetcode 72. Edit Distance
###### tags: `Leetcode(JAVA)`

題目 : https://leetcode.com/problems/edit-distance/ 。

想法 :

題目定義了三個轉移 :
1. Insert
2. Delete
3. Replace

這裡使用Bottom-up DP來完成。
特別要注意邊界條件 :
也就是如果某一方的字串已經被找完了，就回傳另一邊剩餘長度，因剩下全部都用Insert來完成。

有參考別人的寫法(雖然跟我想得差不多)，知道題目是DP後，不能想到窮舉去，不然頭會很痛想不明白。

時間複雜度 : O(n*m)。

程式碼 : (JAVA)

class Solution {
    public int minDistance(String word1, String word2) {
        return editDistance(word1, word2, 0, 0, new Integer[word1.length()][word2.length()]);
    }
    
    private int editDistance(String word1, String word2, int i, int j, Integer[][] dp){
        if(i >= word1.length()){
            return word2.length() - j;
        }
        else if(j >= word2.length()){
            return word1.length() - i;
        }
        
        if(dp[i][j] != null) return dp[i][j];
        if(word1.charAt(i) == word2.charAt(j)){
            return dp[i][j] = editDistance(word1, word2, i+1, j+1, dp);
        }
        else{
            int insert = editDistance(word1, word2, i+1, j, dp);
            int delete = editDistance(word1, word2, i+1, j, dp);
            int replace = editDistance(word1, word2, i+1, j+1, dp);
            return dp[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
        }
    }
}