summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-22 15:39:10 -0600
committerHaidong Ji2018-12-22 15:39:10 -0600
commit0749c0815e49e490cbe4ecdf802a86713fcb0f11 (patch)
tree6da6195979195c84fa2b93981011a8a7c9f5395e
parenta5df8ebce9dcad0b60cf3c381b0e856a0f047ada (diff)
Edit Distance done!
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp105
1 files changed, 41 insertions, 64 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 45bb5fc..373e327 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,81 +1,58 @@
#include <iostream>
-#include <climits>
-#include <vector>
+#include <string>
#include <algorithm>
//#include <gtest/gtest.h>
-using std::vector;
+using std::string;
-vector<int> optimal_sequence(int n) {
- vector<int> sequence;
- int stepsCount[n];
- // the path int array indicates the next step to reduce it:
- // 1: minus 1
- // 2: divide by 2
- // 3: divide by 3
- int path[n];
- int div2Steps, div3Steps, minus1Steps;
- for (int i = 1; i < n; i++) {
- int j = i + 1;
- div2Steps = INT_MAX;
- div3Steps = INT_MAX;
- if (j % 3 == 0) {
- div3Steps = stepsCount[j / 3 - 1];
- }
- if (j % 2 == 0) {
- div2Steps = stepsCount[j / 2 - 1];
- }
- minus1Steps = stepsCount[i - 1];
+int editDistance(const string &A, const string &B) {
+ int m = B.length();
+ int n = A.length();
+ int D[n + 1][m + 1];
- int minStepsCount = std::min(minus1Steps,
- std::min(div2Steps, div3Steps));
- stepsCount[i] = minStepsCount + 1;
- if (minStepsCount == minus1Steps) {
- path[i] = 1;
- continue;
- }
- if (minStepsCount == div2Steps) {
- path[i] = 2;
- continue;
- }
- if (minStepsCount == div3Steps) {
- path[i] = 3;
- }
+ for (int i = 0; i < n + 1; i++) {
+ D[i][0] = i;
}
- sequence.push_back(n);
- while (n > 1) {
- int i = path[n - 1];
- if (i == 3) {
- n = n / 3;
- sequence.push_back(n);
- continue;
- }
- if (i == 2) {
- n = n / 2;
- sequence.push_back(n);
- continue;
+ for (int j = 0; j < m + 1; j++) {
+ D[0][j] = j;
+ }
+
+ for (int j = 1; j < m + 1; j++) {
+ for (int i = 1; i < n + 1; i++) {
+ int insertion = D[i][j - 1] + 1;
+ int deletion = D[i - 1][j] + 1;
+ int match = D[i - 1][j - 1];
+ int mismatch = D[i - 1][j - 1] + 1;
+ if (A.at(i - 1) == B.at(j - 1)) {
+ D[i][j] = std::min(insertion, std::min(deletion, match));
+ } else {
+ D[i][j] = std::min(insertion, std::min(deletion, mismatch));
+ }
}
- n = n - 1;
- sequence.push_back(n);
}
- reverse(sequence.begin(), sequence.end());
- return sequence;
+
+ return D[n][m];
}
-//TEST(PrimitiveCalc, Calc1) {
-// ASSERT_EQ(2, optimal_sequence(6).size() - 1);
+//TEST(EditDistance, d2) {
+// ASSERT_EQ(0, editDistance("ab", "ab"));
+//}
+//TEST(EditDistance, d1) {
+// ASSERT_EQ(1, editDistance("a", "x"));
//}
//
-//TEST(PrimitiveCalc, Calc2) {
-// ASSERT_EQ(14, optimal_sequence(96234).size() - 1);
+//TEST(EditDistance, d3) {
+// ASSERT_EQ(3, editDistance("short", "ports"));
+//}
+//
+//TEST(EditDistance, d4) {
+// ASSERT_EQ(5, editDistance("editing", "distance"));
//}
int main() {
- int n;
- std::cin >> n;
- vector<int> sequence = optimal_sequence(n);
- std::cout << sequence.size() - 1 << std::endl;
- for (size_t i = 0; i < sequence.size(); ++i) {
- std::cout << sequence[i] << " ";
- }
+ string str1;
+ string str2;
+ std::cin >> str1 >> str2;
+ std::cout << editDistance(str1, str2) << std::endl;
+ return 0;
}