编辑距离(一)

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1 , str2 ):
        # write code here
        n = len(str1)
        m = len(str2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        # 初始化 假设有一个字符串为空 那么另一个字符串每一步都需要删除
        for i in range(1, n + 1):
            dp[i][0] = dp[i - 1][0] + 1

        for j in range(1, m + 1):
            dp[0][j] = dp[0][j - 1] + 1
        
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if str1[i - 1] == str2[j - 1]:
                    # 如果该位置字符相等 那么这个位置的操作数等于对角线位置的操作数
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        
        return dp[n][m]

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str1 string字符串
# @param str2 string字符串
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=196&tqId=39377&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=2&tags=&title=
    算法：
        设dp[i][j]表示str1的前i个字符转为str2的前j个字符所需的最少操作数
        初始化：
            dp[0][0] = 0 # 空字符串转为空字符串无需操作
        状态转移方程：
            dp[0][j] = j # 插入j个字符
            dp[i][0] = i # 删除i个字符

            若str1[i - 1] == str2[j - 1]：
                dp[i][j] = dp[i - 1][j - 1]
            否则：
                dp[i][j] =  min(dp[i - 1][j], dp[i][j - 1]) # str1中删除一个字符 或者 str1插入一个字符 或者 替换一个字符
    复杂度：
        时间复杂度：O(m*n)
        空间复杂度：O(m*n)
    """

    def editDistance(self, str1, str2):
        # write code here
        m, n = len(str1), len(str2)

        dp = [[max(n, m)] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = 0

        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

        return dp[m][n]


if __name__ == "__main__":
    sol = Solution()

    # str1, str2 = "nowcoder", "new"

    # str1, str2 = "intention", "execution"

    str1, str2 = "now", "nowcoder"

    # str1, str2 = "now", "new"

    res = sol.editDistance(str1, str2)

    print res