This problem is exactly the same as longest common subsequence problem. Using 2D DP to find the length of LCS
L, and the answer is just
n1 + n2 - L*2.
class Solution(object): def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ n1, n2 = len(word1), len(word2) dp = [ * (n2+1) for _ in range(n1+1)] for i in range(n1): for j in range(n2): dp[i+1][j+1] = dp[i][j] + 1 if word1[i] == word2[j] else max(dp[i+1][j], dp[i][j+1]) return n1 + n2 - dp[n1][n2]*2