# Standard dp solution

• ``````int minDistance(string word1, string word2) {
int  m = word1.length(), n = word2.length();
if (m == 0) return n;
if (n == 0) return m;

// table[i][j]: distance from words1.substr(0, i) to words2.substr(0, j)
int table[m+1][n+1];
for (int i = 0; i <= m; ++i) table[i][0] = i;
for (int j = 0; j <= n; ++j) table[0][j] = j;
// table[i][j] is the min distance between the next three values
// from table[i-1][j], table[i][j-1], or table[i-1][j-1] to table[i][j]
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int cost = (word1[i-1] == word2[j-1] ? 0 : 1);
table[i][j] = min(min(table[i-1][j] + 1, table[i][j-1] + 1), table[i-1][j-1] + cost);
}
}

return table[m][n];
}``````

• Below is my same code in Java

``````public class Solution {
public int minDistance(String word1, String word2) {
if(word1.length() == 0) return word2.length();
if(word2.length() == 0) return word1.length();

int[][] ed = new int[word1.length()+1][word2.length()+1];
for(int i = 0; i<word2.length(); i++){
ed[word1.length()][i] = word2.length() - i;
}
for(int j = 0; j<word1.length(); j++){
ed[j][word2.length()] = word1.length()-j;
}
for(int i = word1.length()-1; i>=0; i--){
for(int j = word2.length()-1; j>=0; j--){
if(word1.charAt(i) == word2.charAt(j)){
ed[i][j] = ed[i+1][j+1];
}else{
ed[i][j] =1+ Math.min(ed[i+1][j+1], Math.min(ed[i+1][j], ed[i][j+1]));
}
}
}
return ed[0][0];
}
}``````

• it think you can make it more clean

• when thinking in dp we have to go from end to front. when implementing using table we have to go from front to end.

• Dijkstra's Algorithm is DP.

• ``````public class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int i = 0; i < dp.length; i++) {
for(int j = 0; j < dp[0].length; j++) {
if(i == 0) dp[i][j] = j;
else if(j == 0) dp[i][j] = i;
else {
int cost = word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1;
dp[i][j] = Math.min(dp[i-1][j-1]+cost,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
}
}
}
return dp[word1.length()][word2.length()];
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.