编辑距离

[问答题]

编辑距离

查看答案及解析

牛客984888733号

动态规划计算编辑距离

发表于 2021-07-26 09:30:23 回复(0)

Leeguohui

编辑距离是衡量两个字符串相似度的一种距离，其说明一个字符串到另外一个字符串需要进过多少次变换（删，增，替换）可以达到相同，变换次数越多两者越不相同，公式1-n/max（a_len，b_len）

流程：1.判断len是否为0，0的话返回一个字符串。

2.构建一个编辑距离矩阵a_len+1，b_len+1。

3.dij=max（di-1j+1，dij-1+1，di-1j-1+temp）

当当前字符相同，说明temp=0，否则=1

发表于 2019-10-31 08:00:45 回复(0)

提交观点

问题信息

上传者：小小

难度：

2条回答 141收藏 1741浏览

扫一扫，把题目装进口袋