首页 > 试题广场 >

最优字符串对齐距离

[编程题]最优字符串对齐距离
  • 热度指数:201 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
实现最优字符串对齐(Optimal String Alignment,OSA)距离的计算。OSA距离是衡量两个字符串相似度的指标,表示将一个字符串转换为另一个字符串所需的最小编辑操作次数。

允许的编辑操作(每个操作代价为1):
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符
4. 交换相邻的两个字符

输入描述:
第一行输入源字符串。
第二行输入目标字符串。


输出描述:
返回一个整数,表示从源字符串转换到目标字符串所需的最小操作次数。
示例1

输入

"caper"
"acer"

输出

2

备注:
1.对应的输入、输出已给出,您只用实现核心功能函数即可。
2.支持numpy、scipy、pandas、scikit-learn库。

这道题你会答吗?花几分钟告诉大家答案吧!