week6_2020101058_lecture_1.md

Edit Distance. Between Two words The minimum number of edit operations to convert it from A to B. insert, delete and replace operation can be the operations. Whenever you apply the dynamic programming. What are the sub-problems should be first question. diff + diagonal. it is to solve the collection of dag problems. Edit distance for words of m and n length will be in time:- O(mn)

So basically in this what we will do is first create a table in which we write all the letters of a word in a column and other in the rows and then start writing the number of operations required to convert this string into the other or vice versa. and The logic which we will give is that "the number of operation will be equal to min+1 of up, left and diagonal and if the last elements of both the words are same then we will just copy the element because then the number of steps required will be the same as the number of steps required in the diagonal".

// A Naive recursive C++ program to find minimum number // operations to convert str1 to str2 #include <bits/stdc++.h> using namespace std;

// Utility function to find minimum of three numbers int min(int x, int y, int z) { return min(min(x, y), z); }

int editDist(string str1, string str2, int m, int n) { // If first string is empty, the only option is to // insert all characters of second string into first if (m == 0) return n;

// If second string is empty, the only option is to
// remove all characters of first string
if (n == 0)
	return m;

// If last characters of two strings are same, nothing
// much to do. Ignore last characters and get count for
// remaining strings.
if (str1[m - 1] == str2[n - 1])
	return editDist(str1, str2, m - 1, n - 1);

// If last characters are not same, consider all three
// operations on last character of first string,
// recursively compute minimum cost for all three
// operations and take minimum of three values.
return 1
	+ min(editDist(str1, str2, m, n - 1), // Insert
			editDist(str1, str2, m - 1, n), // Remove
			editDist(str1, str2, m - 1,
					n - 1) // Replace
		);

}

// Driver code int main() { // your code goes here string str1 = "sunday"; string str2 = "saturday";

cout << editDist(str1, str2, str1.length(),
				str2.length());

return 0;

}

You are encouraged to ignore, if you have better ideas.

in the way you like it.