leetcode 72.编辑距离

class Solution(object):
    def minDistance(self, word1, word2):
        def dp(i,j):
            if i==-1: return j+1
            if j==-1: return i+1
            if word1[i] == word2[j]:
                return dp(i-1,j-1)
            else:
                return min(dp(i,j-1)+1, dp(i-1,j)+1, dp(i-1,j-1)+1)
            return dp(len(word1)-1, len(word2)-1)

class Solution(object):
    def minDistance(self, word1, word2):
        dp_table = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]
            # base case
            for i in range(len(dp_table)):
                dp_table[i][0] = i
            for j in range(len(dp_table[0])):
                dp_table[0][j] = j
            for i in range(1, len(word1)+1):
                for j in range(1, len(word2)+1):
                    if word1[i-1] == word2[j-1]:
                        dp_table[i][j] = dp_table[i-1][j-1]
                    else:
                        dp_table[i][j] = min(dp_table[i-1][j]+1, dp_table[i][j-1]+1, dp_table[i-1][j-1]+1)
            return dp_table[-1][-1]

class Solution(object):
    def minDistance(self, word1, word2):
        class Node:
            def __init__(self, x):
                self.value = x
                ## 0->skip 1->插入 2->删除 3->替换
                self.choice = None

        dp_table = []
        for _ in range(len(word1)+1):
            tmp = []
            for _ in range(len(word2)+1):
                tmp.append(Node(0))
            dp_table.append(tmp)
        
        for i in range(len(dp_table)):
            dp_table[i][0].value = i
        for j in range(len(dp_table[0])):
            dp_table[0][j].value = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp_table[i][j].value = dp_table[i-1][j-1].value
                    dp_table[i][j].choice = 0
                else:
                    table_value_list = [dp_table[i][j-1].value+1, dp_table[i-1][j].value+1, dp_table[i-1][j-1].value+1]
                    dp_table[i][j].choice = table_value_list.index(min(table_value_list))+1
                    dp_table[i][j].value = table_value_list[dp_table[i][j].choice-1]
        return dp_table[-1][-1].value
    def get_choice(self, dp_table):
        i=len(dp_table)-1
        j=len(dp_table[0])-1
        res = []
        while i!=0 or j!=0:
            c = dp_table[i][j].choice
            res.append(c)
            if c == 0 or c == 3:
                i -= 1
                j -= 1
            if c == 1:
                j -= 1
            if c == 2:
                i -= 1
        return res