首页 > 代码库 > [LeetCode] Edit Distance

[LeetCode] Edit Distance

2024-08-04 23:37:15   222人阅读

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。

我写的如下：

 1 #include <iostream> 2 #include <string> 3 #include <memory.h> 4 using namespace std; 5  6 class Solution { 7 public: 8     int minDistance(string word1, string word2) { 9         int len1 = word1.length(),len2=word2.length();10         if(len1==0) return len2;11         if(len2==0) return len1;12         int **dpmap = new int *[len1+1];13         dpmap[0] =new int[(len1+1)*(len2+1)];14         memset(dpmap[0],0,sizeof(int)*(len1+1)*(len2+1));15         for(int i= 1;i<=len1;i++)16             dpmap[i] = dpmap[i-1]+len2+1;17         for(int i=0;i<=len1;i++)18             dpmap[i][0] = i;19         for(int j=0;j<=len2;j++)20             dpmap[0][j] = j;21         for(int i=1;i<=len1;i++){22             for(int j=1;j<=len2;j++){23                 if(word1[i-1]==word2[j-1])  dpmap[i][j]=dpmap[i-1][j-1];24                 else{25                     dpmap[i][j]=(dpmap[i-1][j]>dpmap[i][j-1]?dpmap[i][j-1]:dpmap[i-1][j])+1;26                     if(dpmap[i-1][j-1]+1<dpmap[i][j])27                         dpmap[i][j] = dpmap[i-1][j-1]+1;28                 }29             }30         }31         int ret = dpmap[len1][len2];32 //        for(int i=0;i<=len1;i++){33 //            for(int j=0;j<=len2;j++)34 //                cout<<dpmap[i][j]<<" ";35 //            cout<<endl;36 //        }37         delete []dpmap[0];38         delete []dpmap;39         return ret;40     }41 };42 43 int main()44 {45     string word1 = "123";46     string word2 = "111";47     Solution sol;48     cout<<sol.minDistance(word1,word2)<<endl;49     return 0;50 }
View Code

 

 

 

 

 

 

 

 

[LeetCode] Edit Distance


联系
我们