[python]leetcode(72). Edit Distance AND (583). Delete Operation for Two Strings

problem
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character b) Delete a character c) Replace a character
solution
3つの変更のみを許可します.

文字を削除

文字

を挿入

文字を置換

質問1:

class Solution(object):
    def minDistance(self, word1, word2):
        m = len(word1)
        n = len(word2)
        arr = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m+1):
            arr[i][0] = i
        for i in range(n+1):
            arr[0][i] = i

        for i in range(1, m+1):
            for j in range(1, n+1):
                t = 0 if word1[i-1] == word2[j-1] else 1
                arr[i][j] = min(arr[i-1][j-1]+t, arr[i-1][j]+1, arr[i][j-1]+1)

        return arr[m][n]

質問2:

class Solution(object):
    def minDistance(self, word1, word2):
        m = len(word1)
        n = len(word2)
        arr = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m+1):
            arr[i][0] = i
        for i in range(n+1):
            arr[0][i] = i

        for i in range(1, m+1):
            for j in range(1, n+1):
                t = 0 if word1[i-1] == word2[j-1] else 2 #     
                arr[i][j] = min(arr[i-1][j-1]+t, arr[i-1][j]+1, arr[i][j-1]+1)

        return arr[m][n]

まとめ
この問題は、最も長い共通のサブシーケンスとの関係にあり、この問題では、挿入、削除、置換が許可されています.最長の共通サブシーケンスでは削除のみが許可される編集距離と見なすことができ,異なる編集方式は繰返し方程式で異なるだけであり,コアの方法は現在の2つの文字列がどの2つの文字列から編集できるかにすぎない.つまり,繰返し方程式をどのように書くかを知っている.
もう一つ注意しなければならない点は,最適サブ構造の性質を証明することであり,これは実際には理解しやすいことである.原問題の編集距離が最小の場合,対応する編集距離が最も短いサブ問題が最適であるに違いないからである.
例えば、「abc」と「abb」との間の編集距離は、以下のようにすることができる.

‘ab’, ‘abb’

‘abc’, ‘ab’

「ab」、「ab」(最後の文字を置換する1つに相当)

この3つのサブ問題は,原問題が最適である場合,必ずサブ問題が最適である場合に対応するので,最適サブ構造特性を満たす.
したがって,動的計画解法を用いて解決できる.
その他