aboutsummaryrefslogtreecommitdiff
path: root/other/edit_distance.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/edit_distance.cpp')
-rw-r--r--other/edit_distance.cpp41
1 files changed, 41 insertions, 0 deletions
diff --git a/other/edit_distance.cpp b/other/edit_distance.cpp
new file mode 100644
index 0000000..4103e83
--- /dev/null
+++ b/other/edit_distance.cpp
@@ -0,0 +1,41 @@
+// 72. Edit Distance
+#include "leetcode.h"
+
+/*
+ * given two strings 'word1' and 'word2', return minimum number of operations
+ * required to convert 'word1' to 'word2'. the following operations are
+ * permitted: insert character, delete character, replace character
+ */
+
+class Solution {
+public:
+ int minDistance(string word1, string word2) {
+ int m = word1.size(), n = word2.size();
+ vvd memo(m + 1, vector<int>(n + 1, -1));
+ return editDistance(word1, word2, m, n, memo);
+ }
+
+private:
+ int editDistance(string word1, string word2, int m, int n, vvd memo) {
+ if (m == 0)
+ return memo[m][n] = n;
+ if (n == 0)
+ return memo[m][n] = m;
+ if (memo[m][n] != -1)
+ return memo[m][n];
+ if (word1[m - 1] == word2[n - 1])
+ return memo[m][n] = editDistance(word1, word2, m - 1, n - 1, memo);
+ else {
+ int insertChar = editDistance(word1, word2, m, n - 1, memo);
+ int deleteChar = editDistance(word1, word2, m - 1, n, memo);
+ int replacChar = editDistance(word1, word2, m - 1, n - 1, memo);
+ return memo[m][n] = 1 + min({insertChar, deleteChar, replacChar});
+ }
+ }
+};
+
+int main() {
+ Solution obj;
+ cout << obj.minDistance("horse", "ros") << endl; // expect: 3
+ cout << obj.minDistance("intention", "execution"); // expect: 5
+}