[Leetcode Solution] Edit Distance

Analysis 

• A Dynamic Programming problem we solve by memorization
• Let f[i][j] denote the minimum number of steps to convert word1[1..i] to word2[1..j], then we have
• f[i][j] = min { f[i-1][j] +1, f[i][j-1]+1, f[i-1][j-1]+1,                  f[i-1][j-1] if word1[i]==word2[j]}

Note

Code

UPDATED AT LEETCODE 2ND PASS