[LeetCode] 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

Hide Tags

Dynamic Programming String

一个动态规划的题目，算是简单，不过开始考虑的不够完善。设一个二维数组a[i][j] 其中i 表示 word1 0 to i 字符串，i=0 的时候表示“”，j 同理，那么a 中每项表示 i 字符串转换到 j 字符串的最少步骤。

假如我们已经知道了 <i-1,j-1> <i-1,j> and <i,j-1> 那么 <i,j> 可以如下求得：

word1[i] == word2[j] ，那么可以看作 i-1 字符串和 j-1 字符串各加了一个相同字符，所以<i,j> = <i-1,j-1>
word1[i] != word2[j]

对于<i-1,j-1>，即两字符串后面都加了一个字符且不同，那么 replace 一次就行，所以<i,j> = <i-1,j-1>+1
对于<i,j-1>，即只在 j-1 字符串后面加了一个字符，那么delete 一次就行，<i,j> = <i,j-1>+1
对于<i-1,j>，同<i,j-1>
所以 <i,j> 应该去上面3者最小值

填满整个a 之后 <len1,len2> 为输出结果。

注意项：

a 二维数组需要考虑字符串为""的初始化，所以维度应该+1.
我使用的是堆里面的空间，leetcode 可以直接使用栈空间创建，即不需要new。

我写的如下：

 #include <iostream>

 #include <string>

 #include <memory.h>

 using namespace std;

 class Solution {

 public:

     int minDistance(string word1, string word2) {

         int len1 = word1.length(),len2=word2.length();

         if(len1==) return len2;

         if(len2==) return len1;

         int **dpmap = new int *[len1+];

         dpmap[] =new int[(len1+)*(len2+)];

         memset(dpmap[],,sizeof(int)*(len1+)*(len2+));

         for(int i= ;i<=len1;i++)

             dpmap[i] = dpmap[i-]+len2+;

         for(int i=;i<=len1;i++)

             dpmap[i][] = i;

         for(int j=;j<=len2;j++)

             dpmap[][j] = j;

         for(int i=;i<=len1;i++){

             for(int j=;j<=len2;j++){

                 if(word1[i-]==word2[j-])  dpmap[i][j]=dpmap[i-][j-];

                 else{

                     dpmap[i][j]=(dpmap[i-][j]>dpmap[i][j-]?dpmap[i][j-]:dpmap[i-][j])+;

                     if(dpmap[i-][j-]+<dpmap[i][j])

                         dpmap[i][j] = dpmap[i-][j-]+;

                 }

             }

         }

         int ret = dpmap[len1][len2];

 //        for(int i=0;i<=len1;i++){

 //            for(int j=0;j<=len2;j++)

 //                cout<<dpmap[i][j]<<" ";

 //            cout<<endl;

 //        }

         delete []dpmap[];

         delete []dpmap;

         return ret;

     }

 };

 int main()

 {

     string word1 = "";

     string word2 = "";

     Solution sol;

     cout<<sol.minDistance(word1,word2)<<endl;

     return ;

 }

巴特西

[LeetCode] Edit Distance 字符串变换为另一字符串动态规划

最新文章

热门文章