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

Материал из DISCOPAL
< Участник:DChulkov
Версия от 16:24, 25 мая 2020; DChulkov (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/edit-distance/submissions/ <code-python> class Solution: def minDistance(self, word1: str, word2: str) -> int: L1, L2 =…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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]