72. 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
题目分析
动态规划
对于一个串a和串b,长度为i和j的子串,那么其最小编辑距离有以下两种情况:
1. a[i - 1] == b[j - 1]
2. a[i - 1] != b[j - 1]
情况一,最小编辑距离等于串a[:i - 1]和串b[ : j - 1]的编辑距离.
情况二,最小编辑距离为串a[:i-1]与串b[:j],串a[:i]与串b[: j - 1],串a[:i - 1]与串b[ : j - 1].
优化
该动态规划计算第i层的时候,只依赖第i - 1层.
class Solution {
public:
int minDistance(string word1, string word2) {
vector<int> dp(word2.size() + 1);
for (int i = 0; i <= word2.size(); ++i) {
dp[i] = i;
}
for (int i = 1; i <= word1.size(); ++i) {
int prev = dp[0];
dp[0]++;
for (int j = 1; j <= word2.size(); ++j) {
int dp_store = dp[j];
if (word1[i - 1] == word2[j - 1]) {
dp[j] = prev;
} else {
dp[j] = std::min(std::min(dp[j], dp[j - 1]), prev) + 1;
}
prev = dp_store;
}
}
return dp[word2.size()];
}
};