Python Classic DP
Suppose dp[i][j] records the edit distance between word1[:i] and word2[:j]. And now we proceed to word1[i] and word2[j]. \n1. If they are equal, then edit dista
Suppose ```dp[i][j]``` records the edit distance between ```word1[:i]``` and ```word2[:j]```. And now we proceed to ```word1[i]``` and ```word2[j]```. \n1. If they are equal, then edit distance between ```word1[:i+1]``` and  ```word2[:j+1]``` are the same as ```dp[i][j]```. Or ```dp[i+1][j+1] = dp[i][j]```.\n2. Otherwise, we need to determine which of "delete", "insert", "replace" produces the lowest edit distance. Since each operation cost 1 distance, "delete"\'s cost is 1 extra distance plus edit distance between ```word1[:i]``` and ```word2[:j+1]``` as we delete ```word1[i]```. Or ```dp[i+1][j+1] = dp[i][j+1]+1```. Similiarly, "insert" produces ```dp[i+1][j+1] = dp[i+1][j]+1``` and "replace" produces ```dp[i+1][j+1] = dp[i][j]+1```. And we just pick the minimum from these three.\n\nThus, our recurrsion equation is \n```\ndp[i+1][j+1] = dp[i][j] if word1[i]==word2[j] else min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1\n```\nOne head row and left column are inserted in dp array for base. We can viewed it as each word has an empty string at the begining and empty string is not equal to any character. So initially, ```dp[0][j] = j``` and ```dp[i][0] = i```\n```\ndef minDistance(word1, word2):\n\tm, n = len(word1), len(word2)\n\tdp = [list(range(n+1))]+[[r+1]+[0]*n for r in range(m)]\n\tfor i in range(m):\n\t\tfor j in range(n):\n\t\t\tdp[i+1][j+1] = dp[i][j] if word1[i]==word2[j] else min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1\n\treturn dp[m][n]\n```\nBoth time and space complexity is O(mn). m, n stands for length of word1 and word2.\nAnd we can implement a rolling1D DP since only two rows of DP table are actually used. So space complexity could be reduced to O(min(m,n)):\n```\ndef minDistance(word1, word2):\n\tm, n = len(word1), len(word2)  # switch word1 and word2 if m < n to ensure n \u2264 m\n\tcurr = list(range(n+1))\n\tfor i in range(m):\n\t\tprev, curr = curr, [i+1] + [0] * n\n\t\tfor j in range(n):\n\t\t\tcurr[j+1] = prev[j] if word1[i] == word2[j] else min(curr[j], prev[j], prev[j+1]) + 1\n\treturn curr[n]\n```
['Python']