Python3 计算字符串变换相等的最小操作代价 2020远景智能计算字符串相似度

计算字符串变换相等的最小操作代价 2020远景智能计算字符串相似度计算字符串变换相等的最小操作代价题目描述:输入描述:输出描述:示例:思路:算法介绍示例代码:代码输出:2020远景智能在线笔试 计算字符串的相似度题目描述:输入描述:输出描述:示例:思路:示例代码代码输出
计算字符串变换相等的最小操作代价
题目描述:

定义一套操作方法来把两个字符串变得相同,如下:
1、增加一个字符,如把’a’替换为’b’。 操作一步的代价为add_cost。
2、删除一个字符,如把’abdd’变为’aebdd’。 操作一步的代价为del_cost。
3、修改一个字符,如把’travelling’变为’traveling’。操作一步的代价为modify_cost。
比如,对于’abcdef’和’abcdefg’两个字符串来说,可以通过增加或者删除一个’g’来实现目的,两种方案均只需要操作一次,代价可能不同。
当 add_cost = del_cost = modify_cost = 1 时,这个最小操作次数等于最小操作代价。
比如,’abcdef’和’abcdefg’两个字符串,最小操作次数为1,最小操作代价为min(add_cost, del_cost)。
给定两个任意的字符串,写一个算法计算它们的最小操作代价。

输入描述:

前两行输入两个字符串
第三行分别为add_cost、del_cost、modify_cost。

输出描述:

输出最小操作代价

示例:

输入:

abcdef
abcdefg
1 1 1

输出:

1

思路:

动态规划,dp[i][j]表示将str1[0…i-1]编辑成str2[0…j-1]的最小操作代价
例如,特殊的dp[0][0] = 0,
dp[1][0]表示str1[0]编辑成空字符串’’的最小操作代价
注意:将str1编辑成str2的最小操作代价可能不等于将str2编辑成str1的最小操作代价

算法介绍

动态规划算法介绍: B站算法视频

示例代码:
'''
计算字符串变换相等的最小操作代价
题目描述:
定义一套操作方法来把两个字符串变得相同,如下:
1、增加一个字符,如把'a'替换为'b'。 操作一步的代价为add_cost。
2、删除一个字符,如把'abdd'变为'aebdd'。 操作一步的代价为del_cost。
3、修改一个字符,如把'travelling'变为'traveling'。操作一步的代价为modify_cost。
比如,对于'abcdef'和'abcdefg'两个字符串来说,可以通过增加或者删除一个'g'来实现目的,两种方案均只需要操作一次,代价可能不同。
当 add_cost = del_cost = modify_cost = 1 时,这个最小操作次数等于最小操作代价。
比如,'abcdef'和'abcdefg'两个字符串,最小操作次数为1,最小操作代价为min(add_cost, del_cost)。
给定两个任意的字符串,写一个算法计算它们的最小操作代价。
输入描述:
前两行输入两个字符串
第三行分别为add_cost、del_cost、modify_cost。
输出描述:
输出最小操作代价
示例:
输入:
abcdef
abcdefg
1 1 1
输出
1
思路:动态规划,dp[i][j]表示将str1[0...i-1]编辑成str2[0...j-1]的最小操作代价
例如,特殊的dp[0][0] = 0,
dp[1][0]表示str1[0]编辑成空字符串''的最小操作代价
注意:将str1编辑成str2的最小操作代价可能不等于将str2编辑成str1的最小操作代价
'''
def min_cost(str1, str2): #增加字符、删除字符、修改字符的操作代价分别为add_cost, del_cost, modify_cost
dp = [[0]*(len(str2)+1) for _ in range(len(str1)+1)] for i in range(len(str1)+1): #二维数组dp第一列赋值
dp[i][0] = i * del_cost
for j in range(len(str2)+1): #二维数组dp第一行赋值
dp[0][j] = j * add_cost
for i in range(1, len(str1)+1):
for j in range(1,len(str2)+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] else:
dp[i][j] = dp[i-1][j-1] + modify_cost
dp[i][j] = min(dp[i][j], dp[i][j-1] + add_cost, dp[i-1][j] + del_cost)
return dp[-1][-1]

'''# 输入
str1 = input().strip()
str2 = input().strip()
add_cost, del_cost, modify_cost = list(map(int, input().split()))
'''
str1 = 'abcdef'
str2 = 'abcdefg'
add_cost, del_cost, modify_cost = 1, 2, 3

min_cost_1_to_2 = min_cost(str1, str2)
min_cost_2_to_1 = min_cost(str2, str1)

print('###################################################计算字符串变换相等的最小操作代价')
print('输入的两个字符串为: ', str1, '与', str2)
print('增加字符、删除字符、修改字符的操作代价分别为:', add_cost, del_cost, modify_cost)
print('将str1编辑成str2的最小操作代价为: ', min_cost_1_to_2)
print('将str2编辑成str1的最小操作代价为: ', min_cost_2_to_1)
print('两字符串的最终最小操作代价为: ', min(min_cost_1_to_2, min_cost_2_to_1))
print('###################################################')

代码输出:
###################################################计算字符串变换相等的最小操作代价
输入的两个字符串为: abcdef 与 abcdefg
增加字符、删除字符、修改字符的操作代价分别为: 1 2 3
将str1编辑成str2的最小操作代价为: 1
将str2编辑成str1的最小操作代价为: 2
两字符串的最终最小操作代价为: 1
###################################################

2020远景智能在线笔试 计算字符串的相似度
题目描述:

定义一套操作方法来把两个字符串变得相同,如下:
1、增加一个字符,如把’a’替换为’b’。
2、删除一个字符,如把’abdd’变为’aebdd’。
3、修改一个字符,如把’travelling’变为’traveling’。
比如,对于’abcdef’和’abcdefg’两个字符串来说,可以通过增加或者删除一个’g’来实现目的,两种方案均只需要操作一次。
把这个最小的操作次数定义为两个字符串之间的距离,而相似度等于‘距离+1’的倒数。
比如,’abcdef’和’abcdefg’两个字符串,距离为1,相似度为1/2。
给定两个任意的字符串,写一个算法计算它们的相似度。

输入描述:

输入两个字符串

输出描述:

输出相似度,string类型

示例:

输入:

abcdef
abcdefg

输出:

1/2

思路:

动态规划,dp[i][j]表示将str1[0…i-1]编辑成str2[0…j-1]的操作次数
例如,特殊的dp[0][0] = 0,
dp[1][0]表示str1[0]编辑成空字符串’’的操作数
注意:将str1编辑成str2的最小操作数等于将str2编辑成str1的最小操作数

示例代码
def min_cost(str1, str2):
dp = [[0]*(len(str2)+1) for _ in range(len(str1)+1)] for i in range(len(str1)+1): #二维数组dp第一列赋值
dp[i][0] = i
for j in range(len(str2)+1): #二维数组dp第一行赋值
dp[0][j] = j
for i in range(1, len(str1)+1):
for j in range(1,len(str2)+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1] else:
dp[i][j] = 1 + dp[i-1][j-1] dp[i][j] = min(dp[i][j], dp[i][j-1] + 1, dp[i-1][j] + 1)
return dp[-1][-1]

'''# 输入
str1 = input().strip()
str2 = input().strip()
'''
str1 = 'abcdef'
str2 = 'abcdefg'

distance = min_cost(str1, str2)
#print('1/'+str(distance + 1))

print('###################################################2020远景智能在线笔试 计算字符串的相似度')
print('输入的两个字符串为: ', str1, '与', str2)
print('两个字符串之间的距离为: ', distance)
print('两个字符串之间的相似度为:', '1/'+str(distance + 1))
print('###################################################')

代码输出
###################################################2020远景智能在线笔试 计算字符串的相似度
输入的两个字符串为: abcdef 与 abcdefg
两个字符串之间的距离为: 1
两个字符串之间的相似度为: 1/2
###################################################


作者:SS_此心安处是吾乡

相关推荐

一文快速搞懂Springboot发送邮件操作

一文快速搞懂Springboot发送邮件操作

for循环中如何正确使用字符串拼接

标准C++ 文件操作学习笔记

习惯了oracle10g写法的朋友们注意了,oralce11g有变化了,小谈空字符串与null的区别