Delete Operation for Two Strings

Intuition

Solution

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        """
        Main part is to caculate longest common subquence
        """
        if not word1 or not word2:
            return len(word1) + len(word2)
        length = [0] * len(word1)
        for c in word2:
            tmp = []
            for j in range(len(word1)):
                if word1[j] == c:
                    if j == 0:
                        tmp.append(1)
                    else:
                        tmp.append(max(length[j - 1] + 1, length[j]))
                else:
                    if j == 0:
                        tmp.append(length[j])
                    else:
                        tmp.append(max(tmp[j - 1], length[j]))
            length = tmp
        l = max(length)
        return len(word1) + len(word2) - 2 * l