Участник:DChulkov/Leet5

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/edit-distance/submissions/

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        L1, L2 = len(word1), len(word2)
        p = [[0] * (L2 + 1) for _ in range(L1 + 1)]
        for i in range(L1 + 1):
            p[i][0] = i
        for j in range(L2 + 1):
            p[0][j] = j
        for i in range(1, L1 + 1):
            for j in range(1, L2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    p[i][j] = p[i - 1][j - 1]
                else:
                    p[i][j] = min(p[i - 1][j - 1], p[i - 1][j], p[i][j - 1]) + 1
        return p[L1][L2]