http://www.lintcode.com/en/problem/edit-distance/

2016-08-29

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法：

• 插入一个字符
• 删除一个字符
• 替换一个字符

样例

给出 work1="mart" 和 work2="karma"

返回 3

标签： 动态规划

 

解题：

此题为典型的动态规划问题，可以按照一般解题思路解决。

 

首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

 

显然可以有如下动态规划公式：

 

• if i == 0 且 j == 0，edit(i, j) = 0
• if i == 0 且 j > 0，edit(i, j) = j
• if i > 0 且j == 0，edit(i, j) = i
• if i ≥ 1  且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

实现代码如下：

class Solution {public:        /**     * @param word1 & word2: Two string.     * @return: The minimum number of steps.     */    int minDistance(string word1, string word2) {        // write your code here        //@@@@@动态规划解题套路@@@@@        //可以通过具体举例，模拟执行过程，绘制表格来找出规律！！！                int w1=word1.length();        int w2=word2.length();        int dp[w1+1][w2+1];        dp[0][0]=0;                for(int i=0;i

总结：遇到这类题目，可以用套路来解题。不同的是，需要根据不同的要求写出某个子问题的解的表达式。有些可能不能直接一眼看出他们的关系，所以

           需要自己通过具体举例，模拟执行过程，最终归纳出结果。（多思考）