1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for(int i = 1; i <= word1.size(); ++i)
dp[i][0] = i;
for(int i = 1; i <= word2.size(); ++i)
dp[0][i] = i;
for(int i = 1; i <= word1.size(); ++i)
{
for(int j = 1; j <= word2.size(); ++j)
{
if(word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
}
}
return dp.back().back();
}
};
|
T(n) : O(n^2)
S(n) : O(n^2)
动态规划
设dp[i][j]代表从word1[0...i)转到word2[0...j)所需的最小次数。假设已知dp[i - 1][j - 1]，即word1[0...i - 1)转到word2[0...j - 1)所需的最小步数，此时可保证，将面临一些几种情况，此时可保证word1[0...i - 1) == word2[0...j - 1)。
- 当
word1[i - 1] == word2[j - 1], 则dp[i][j] = dp[i - 1][j - 1]。
- 当
word1[i - 1] != word2[j - 1], 则可以replace(word1[i - 1], word2[j - 1])，dp[i][j] = dp[i - 1][j - 1] + 1。
- 当
word1[0...i - 1) == word2[0...j)，则可以delete(word1[i - 1])，dp[i][j] = dp[i - 1][j] + 1。
- 当
word1[0...i - 1) + word2[j - 1] == word2[0...j)，则可以insert(word2[j - 1])，dp[i][j] = dp[i][j - 1] + 1。 对于后三种情况，需要获得最小的步数，因此取最小值即可忽略复杂的判断(考虑replace，insert，delete)三种操作
base:
dp[i][0] = i，所有word[0...i)转到0长度都需要删掉i个数字dp[0][j] = j，同理
optimize space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minDistance(string word1, string word2) {
vector<int> dp(word2.size() + 1, 0);
for(int i = 1; i <= word2.size(); ++i)
dp[i] = i;
for(int i = 1; i <= word1.size(); ++i)
{
int prev = dp[0];
dp[0] = i;
for(int j = 1; j <= word2.size(); ++j)
{
auto tmp = dp[j];
if(word1[i - 1] == word2[j - 1])
dp[j] = prev;
else
dp[j] = min(min(dp[j - 1], dp[j]), prev) + 1;
prev = tmp;
}
}
return dp.back();
}
};
|
优化方式参考221. Maximal Square
注意这里需要每次更新dp[0]用做base