From 0749c0815e49e490cbe4ecdf802a86713fcb0f11 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 22 Dec 2018 15:39:10 -0600
Subject: Edit Distance done!

---
 PlaygroundCpp/Sources/Playground.cpp | 105 ++++++++++++++---------------------
 1 file 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;
 }
-- 
cgit v1.2.3