# 0072. Edit Distance ###### tags: `Leetcode` `Medium` `Dynamic Programming` Link: https://leetcode.com/problems/edit-distance/[mapquest driving directions](https://mapquestdrivingdirections.app/) ## 思路 ```dp[i][j]```表示```word1.substring(0,i+1)```和```word2.substring(0,j+1)```的minimum edit distance 如果```word1.charAt(i)==word2.charAt(j)``` 说明edit distance等于```dp[i-1][j-1]``` 如果不等 那么可以delete add 或者replace ```dp[i-1][j]```说明我们要delete word1的一个字母或者add char `j`到word1 ```dp[i][j-1]```说明我们要delete word2的一个字母或者add char `i`到word2 ```dp[i-1][j-1]```表示我们要replace ## Code ```java= class Solution { public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m+1][n+1]; for(int i=1; i<=m; i++) dp[i][0] = i; for(int i=1; i<=n; i++) dp[0][i] = i; for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1; } } return dp[m][n]; } } ```