no-plagiarism

Description
IIT Gandhinagar has a strong policy against plagiarism. The institute decides to develop a program that measures how different two texts are from each other. Suppose there are two text strings A and B, the program should be able to calculate the minimum number of characters that must be added to and/or removed from A to get B, called Dissimilarity (or equivalently, the total
numbers of characters that must be added to A and B to make them equal).

Input Format
First line contains A
Second line contains B

Output Format
One line containing the Dissimilarity of A to B

Input Limits
0 < Length(A), Length(B) < 200

SAMPLE INPUT
written word
kitten purred

SAMPLE OUTPUT
9

Explanation

For example if A is "written word" and B is "kitten purred" we can delete 4 characters from A to get "itten rd" and then add 5 new ones(k,p,u,r,e) to get B, such that the total number of characters added or removed from A to get B count to 9. Therefore we define the Dissimilarity of A from B to be 9.

You are required to write the program to compute the dissimilarity of two texts.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def editDistance(str1, str2, m, n):
	dp = [[0 for x in range(n+1)] for x in range(m+1)]
	for i in range(m+1):
		for j in range(n+1):
			if i == 0:
				dp[i][j] = j    
			elif j == 0:
				dp[i][j] = i
			elif str1[i-1] == str2[j-1]:
				dp[i][j] = dp[i-1][j-1]
			else:
				dp[i][j] = 1 + min(dp[i][j-1],dp[i-1][j])

	return dp[m][n]

s1 = input()
s2 = input()

print((editDistance(s1,s2,len(s1),len(s2))))


def editDistDP(str1, str2, m, n):
	# Create a table to store results of subproblems
	dp = [[0 for x in range(n+1)] for x in range(m+1)]
 
	# Fill d[][] in bottom up manner
	for i in range(m+1):
		for j in range(n+1):
 
			# If first string is empty, only option is to
			# isnert all characters of second string
			if i == 0:
				dp[i][j] = j    # Min. operations = j
 
			# If second string is empty, only option is to
			# remove all characters of second string
			elif j == 0:
				dp[i][j] = i    # Min. operations = i
 
			# If last characters are same, ignore last char
			# and recur for remaining string
			elif str1[i-1] == str2[j-1]:
				dp[i][j] = dp[i-1][j-1]
 
			# If last character are different, consider all
			# possibilities and find minimum
			else:
				dp[i][j] = 1 + min(dp[i][j-1],        # Insert
								   dp[i-1][j])        # Remove
 
	return dp[m][n]

# Driver program to test the above function
str1 = input()
str2 = input()
print(editDistDP(str1, str2, len(str1), len(str2)))

# This code is contributed by Bhavya Jain