aboutsummaryrefslogtreecommitdiff
path: root/other/delete_operation_2string.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/delete_operation_2string.cpp')
-rw-r--r--other/delete_operation_2string.cpp26
1 files changed, 26 insertions, 0 deletions
diff --git a/other/delete_operation_2string.cpp b/other/delete_operation_2string.cpp
new file mode 100644
index 0000000..b6e38e4
--- /dev/null
+++ b/other/delete_operation_2string.cpp
@@ -0,0 +1,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);
+}