最小编辑代价

[编程题]最小编辑代价

热度指数：3329 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

输入描述:

输出三行，第一行和第二行均为一行字符串，分别表示两个字符串str1，str2。。第三行为三个正整数，代表ic，dc和rc。（1<=ic<=10000、1<=dc<=10000、1<=rc<=10000）

输出描述:

输出一个整数，表示编辑的最小代价。

示例1

输入

abc
adc
5 3 2

输出

示例2

输入

abc
adc
5 3 100

输出

示例3

输入

abc
abc
5 3 2

输出

备注:

时间复杂度，空间复杂度。(n,m代表两个字符串长度)

算法知识视频讲解

Python

牛客89223907号

所以python是无论如何都过不了了？一直提示：您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

def distance(str1, str2, ic, dc, rc):
    len1, len2 = len(str1) + 1, len(str2) + 1
    dp = [0]
    for i in range(1, len2):
        dp.append(dp[i-1] + ic)
    #print(dp)
    for i in range(1, len1):
        last = dp[0]
        dp[0] = i * dc
        for j in range(1, len2):
            tmp = dp[j]
            dp[j] = min(dp[j] + dc, dp[j-1] + ic)
            if str1[i - 1] == str2[j - 1]:
                dp[j] = min(dp[j], last)
            else:
                dp[j] = min(dp[j], last + rc)
            last = tmp
    #print(dp)
    return dp[-1]


if __name__ == '__main__':
    try:
        str1 = input()
        str2 = input()
        ic, dc, rc = map(int, input().split())
        if not str1&nbs***bsp;len(str1) > 5000:
            print('0')
        if not str2&nbs***bsp;len(str2) > 5000:
            print('0')
        if ic == 0&nbs***bsp;dc == 0&nbs***bsp;rc == 0&nbs***bsp;ic > 10000&nbs***bsp;dc > 10000&nbs***bsp;rc > 10000:
            print('0')
        print(distance(str1, str2, ic, dc, rc))
    except:
        pass

发表于 2019-12-22 00:09:20 回复(1)