55namespace minimum_edit_distance {
68uint64_t
min(uint64_t x, uint64_t y, uint64_t z) {
69 if (x <= y && x <= z) {
72 if (y <= x && y <= z) {
92uint64_t
editDistDP(std::string str1, std::string str2, uint64_t m,
95 std::vector<std::vector<uint64_t>>
dp(
97 std::vector<uint64_t>(
102 for (uint64_t i = 0; i <= m; i++) {
103 for (uint64_t j = 0; j <= n; j++) {
118 else if (str1[i - 1] == str2[j - 1]) {
119 dp[i][j] =
dp[i - 1][j - 1];
125 dp[i][j] = 1 +
min(
dp[i][j - 1],
144 std::string str1 =
"INTENTION";
145 std::string str2 =
"EXECUTION";
146 uint64_t expected_output1 = 5;
148 str1, str2, str1.length(),
153 std::cout <<
"Minimum Number of Operations Required: " << output1
157 std::string str3 =
"SATURDAY";
158 std::string str4 =
"SUNDAY";
159 uint64_t expected_output2 = 3;
161 str3, str4, str3.length(), str4.length());
162 assert(output2 == expected_output2);
163 std::cout <<
"Minimum Number of Operations Required: " << output2
173int main(
int argc,
char *argv[]) {
uint64_t min(uint64_t x, uint64_t y, uint64_t z)
Takes input of the cost of three operations: Insert, Replace and Delete and return the minimum cost a...
static void test()
Self-test implementations.
uint64_t editDistDP(std::string str1, std::string str2, uint64_t m, uint64_t n)
Calculates and stores the result of all the sub-problems, so that we don't have to recur to compute t...
Dynamic Programming algorithms.