Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
Example 2:
Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)
优化后的递归程序
用d_ 二维向量来存储 word1前i个字符 变化到 word2前j个字符 所需的步骤1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
//static int step;
vector<vector<int>> d_;
int minDistance(string word1, string word2) {
int l1=word1.length();
int l2=word2.length();
d_=vector<vector<int>>(l1+1,vector<int>(l2+1,-1));
//空串到空串 变化就是0次，所以初始化向量为-1
return M(word1,word2,l1,l2);
}
long M(string &word1,string &word2,int i,int j){
long steps;
//if(i==0&&j==0) return 0;
if(d_[i][j]>=0) return d_[i][j];
if(i==0) return j;
if(j==0) return i;
if(word1[i-1]==word2[j-1]) return M(word1,word2,i-1,j-1);
steps=1+min(min(M(word1,word2,i-1,j-1),M(word1,word2,i,j-1)),M(word1,word2,i-1,j));
return d_[i][j]=steps;
}
};
之前的递归程序 栈递归 溢出time exceeded
反复计算 所以可以优化递归 存储中间结果1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
//static int step;
int minDistance(string word1, string word2) {
return M(word1,word2,word1.length(),word2.length());
}
long M(string &word1,string &word2,int i,int j){
long steps;
//if(i==0&&j==0) return 0;
if(i==0) return j;
if(j==0) return i;
if(word1[i-1]==word2[j-1]) return M(word1,word2,i-1,j-1);
steps=1+min(min(M(word1,word2,i-1,j-1),M(word1,word2,i,j-1)),M(word1,word2,i-1,j));
return steps;
}
};