blob: b6e38e4414fc8519b4fb87ddc92dd932b3b32b17 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include "leetcode.h"
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
if (m < n) {
swap(word1, word2);
swap(n, m);
}
vector<int> last(n + 1, 0), curr(n + 1, 0);
for (char char1 : word1) {
for (int i = 0; i < n; i++)
curr[i + 1] =
char1 == word2[i] ? last[i] + 1 : max(curr[i], last[i + 1]);
swap(last, curr);
}
return m + n - 2 * last[n];
}
};
int main() {
Solution obj;
string word1 = "sea", word2 = "eat";
cout << obj.minDistance(word1, word2);
}
|