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(-) (limited to 'PlaygroundCpp') 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 -#include -#include +#include #include //#include -using std::vector; +using std::string; -vector optimal_sequence(int n) { - vector 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 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