Lintcode119|Lintcode119 Edit Distance solution 题解

2022-07-18

【题目描述】

Given two wordsword1andword2, 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:
·Insert a character
·Delete a character
·Replace a character
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法：
·插入一个字符
·删除一个字符
·替换一个字符
【题目链接】
www.lintcode.com/en/problem/edit-distance/
【题目解析】
ed[i][j]表示将word1的前i个字符变成word2的前j个字符所需要的最少操作。
初始化：
【Lintcode119|Lintcode119 Edit Distance solution 题解】ed[i][0]=i 删除i次
ed[0][j]=j 添加j次
状态函数：
如果word1.charAt(i-1)==word2.charAt(j-1)
ed[i][j]=min(min(ed[i-1][j], ed[i][j-1])+1, ed[i-1][j-1])
否则
ed[i][j]=min(min(ed[i-1][j], ed[i][j-1])+1, ed[i-1][j-1]+1)
即word1的前i为字符转换为word2的前j位字符所需的最小操作有三种情况要讨论：
1）将word1的第i位字符删去。此时只要看word1的前i－1位字符转换为word2的前j位字符所需操作再加上刚才的删除操作。
2）将word2的第j位字符删去。此时只要看word1的前i位字符转换为word2的前j－1位字符所需操作再加上刚才的删除操作。
3）将word1的第i位字符转换为word2的第j位字符。此时又分两种情况：1）word1的第i位字符和word2的第j位字符相等，则对于word1的第i位字符和word2的第j位字符无序任何操作，直接看word1的前i－1位字符转换为word2的前j－1位字符所需操作2）word1的第i位字符和word2的第j位字符不相等，则要将word1的第i位字符转换为word2的第j位字符，然后就是1）的情况。
这三种情况里面的最小值就是ed[i][j]的值。
【参考答案】
www.jiuzhang.com/solutions/edit-distance/

推荐阅读

上一篇：小体积干簧继电器在工业中的运用优势

下一篇：五十一|五十一玩笑玩腻了静默旁听者