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。输出描述：输出最小操作代价示例：输入：abcdefabcdefg1 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_costdp = [[0]*(len(str2)+1) for _ in range(len(str1)+1)]for i in range(len(str1)+1):              #二维数组dp第一列赋值dp[i][0] = i * del_costfor j in range(len(str2)+1):              #二维数组dp第一行赋值dp[0][j] = j * add_costfor 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_costdp[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, 3min_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] = ifor j in range(len(str2)+1):              #二维数组dp第一行赋值dp[0][j] = jfor 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
###################################################

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！