雅乐网

计算机技术、学习成长

编程 » OJ刷题 » 【OJ】72. Edit Distance 编辑距离

【OJ】72. Edit Distance 编辑距离

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

思路

d[i][j]表示word1的前i个字符到word2的前j个字符的距离

一、word1[i] == word2[j] 时, d[i][j] = d[i-1][j-1]

二、word1[i] != word2[j] 时,取下面三种情况的最小者

1. d[i-1][j] + 1 (添加)

2. d[i][j-1] + 1 (删除)

3. d[i-1][j-1] + 1 (替换)

初始条件:

d[i][0] = i

d[0][j] = j

代码

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/oj_leetcode_72_edit_distance.html

上一篇:

下一篇:

我要评论

验证码*: 6 + 6 =