Given two strings s and t. Return the minimum number of operations required to convert s to t.
The possible operations are permitted:
	Insert a character at any position of the string.
	Remove any character from the string.
	Replace any character from the string with any other character.
 
Example 1:
Input: 
s = "geek", t = "gesek"
Output: 1
Explanation: One operation is required 
inserting 's' between two 'e's of s.
Example 2:
Input : 
s = "gfg", t = "gfg"
Output: 
0
Explanation: Both strings are same.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function editDistance() which takes strings s and t as input parameters and returns the minimum number of operation to convert the string s to string t. 
Expected Time Complexity: O(|s|*|t|)
Expected Space Complexity: O(|s|*|t|)
Constraints:
1 ≤ Length of both strings ≤ 100
Both the strings are in lowercase.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: class Solution:

	def editDistance(self, s, t):

		# Code here

Solutions:
class Solution:

	def editDistance(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				dp[i][0] = i
				dp[0][j] = j
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
		return dp[n][m]


class Solution:

	def editDistance(self, s, t):
		mat = []
		for i in range(len(s) + 1):
			mat.append([i])
		for j in range(len(t)):
			mat[0].append(j + 1)
		for i in range(len(s)):
			for j in range(len(t)):
				if s[i] == t[j]:
					mat[i + 1].append(mat[i][j])
				else:
					mat[i + 1].append(min(mat[i][j], mat[i + 1][j], mat[i][j + 1]) + 1)
		return mat[len(s)][len(t)]


class Solution:

	def editDistance(self, word1, word2):
		n = len(word1)
		m = len(word2)
		t = [[0 for p in range(0, m + 1)] for q in range(0, n + 1)]
		for a in range(0, n + 1):
			t[a][0] = a
		for b in range(1, m + 1):
			t[0][b] = b
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if word1[i - 1] == word2[j - 1]:
					t[i][j] = t[i - 1][j - 1]
				else:
					t[i][j] = 1 + min(t[i][j - 1], t[i - 1][j], t[i - 1][j - 1])
		return t[n][m]


class Solution:

	def editDistance(self, s, t):
		dp = [[float('inf')] * (len(t) + 1) for i in range(len(s) + 1)]
		for k in range(len(s) + 1):
			dp[k][len(t)] = len(s) - k
		for k in range(len(t) + 1):
			dp[len(s)][k] = len(t) - k
		for i in range(len(s) - 1, -1, -1):
			for j in range(len(t) - 1, -1, -1):
				if s[i] == t[j]:
					dp[i][j] = dp[i + 1][j + 1]
				else:
					dp[i][j] = 1 + min(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
		return dp[0][0]


class Solution:

	def editDistance(self, s, t):

		def fun(i, j):
			if i < 0:
				return j + 1
			if j < 0:
				return i + 1
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == t[j]:
				return 0 + fun(i - 1, j - 1)
			else:
				dp[i][j] = min(1 + fun(i, j - 1), 1 + fun(i - 1, j), 1 + fun(i - 1, j - 1))
			return dp[i][j]
		row = len(s)
		col = len(t)
		dp = [[-1 for j in range(col)] for i in range(row)]
		i = len(s) - 1
		j = len(t) - 1
		return fun(i, j)


class Solution:

	def solve(self, s1, s2, i, j, dp):
		if i == len(s1):
			return len(s2) - j
		if j == len(s2):
			return len(s1) - i
		if dp[i][j] != -1:
			return dp[i][j]
		ans = 0
		if s1[i] == s2[j]:
			return self.solve(s1, s2, i + 1, j + 1, dp)
		else:
			ins = 1 + self.solve(s1, s2, i, j + 1, dp)
			delt = 1 + self.solve(s1, s2, i + 1, j, dp)
			repl = 1 + self.solve(s1, s2, i + 1, j + 1, dp)
			ans = min(ins, min(delt, repl))
		dp[i][j] = ans
		return dp[i][j]

	def editDistance(self, s, t):
		i = 0
		j = 0
		dp = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]
		return self.solve(s, t, i, j, dp)


class Solution:

	def editDistance(self, s, t):
		n = len(s)
		m = len(t)
		prev = [j for j in range(m + 1)]
		curr = [0] * (m + 1)
		for i in range(1, n + 1):
			curr[0] = i
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					curr[j] = prev[j - 1]
				else:
					mn = min(1 + prev[j], 1 + curr[j - 1])
					curr[j] = min(mn, 1 + prev[j - 1])
			prev = curr.copy()
		return prev[m]


class Solution:

	def solve(self, i, j, m, n, s, t, dp):
		if i == m and j == n:
			return 0
		if j == n:
			return m - i
		if i == m:
			return n - j
		if dp[i][j] != -1:
			return dp[i][j]
		if s[i] == t[j]:
			dp[i][j] = self.solve(i + 1, j + 1, m, n, s, t, dp)
			return dp[i][j]
		else:
			dp[i][j] = min(self.solve(i, j + 1, m, n, s, t, dp), self.solve(i + 1, j, m, n, s, t, dp), self.solve(i + 1, j + 1, m, n, s, t, dp)) + 1
			return dp[i][j]

	def editDistance(self, s, t):
		dp = [[-1] * len(t) for _ in range(len(s))]
		x = self.solve(0, 0, len(s), len(t), s, t, dp)
		return x


class Solution:

	def editDistance(self, s, t):
		dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]
		for i in range(len(t) + 1):
			for j in range(len(s) + 1):
				if i == 0:
					dp[i][j] = j
				elif j == 0:
					dp[i][j] = i
				elif s[j - 1] == t[i - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
		return dp[-1][-1]


class Solution:

	def solution(self, s, t, i, j, dp):
		if i == 0:
			return j
		if j == 0:
			return i
		if dp[i][j] != -1:
			return dp[i][j]
		if s[i - 1] == t[j - 1]:
			return 0 + self.solution(s, t, i - 1, j - 1, dp)
		else:
			insert = 1 + self.solution(s, t, i, j - 1, dp)
			delete = 1 + self.solution(s, t, i - 1, j, dp)
			replace = 1 + self.solution(s, t, i - 1, j - 1, dp)
		dp[i][j] = min(insert, min(replace, delete))
		return dp[i][j]

	def editDistance(self, s, t):
		dp = [[0] * (len(t) + 1) for row in range(len(s) + 1)]
		for i in range(len(s) + 1):
			dp[i][0] = i
		for j in range(len(t) + 1):
			dp[0][j] = j
		for i in range(1, len(s) + 1):
			for j in range(1, len(t) + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = 0 + dp[i - 1][j - 1]
				else:
					dp[i][j] = min(1 + dp[i][j - 1], min(1 + dp[i - 1][j - 1], 1 + dp[i - 1][j]))
		return dp[i][j]


class Solution:

	def editDistance(self, s, t):
		n = len(s)
		m = len(t)
		prev = [0 for i in range(m + 1)]
		for j in range(1, m + 1):
			prev[j] = j
		for i in range(1, n + 1):
			temp = [0 for i in range(m + 1)]
			temp[0] = i
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					temp[j] = prev[j - 1]
				else:
					insert = 1 + temp[j - 1]
					delete = 1 + prev[j]
					replace = 1 + prev[j - 1]
					temp[j] = min(insert, delete, replace)
			prev = temp
		return prev[m]


class Solution:

	def editDistance(self, str1, str2):
		(small, large) = (None, None)
		if len(str1) < len(str2):
			(small, large) = (str1, str2)
		else:
			(small, large) = (str2, str1)
		(m, n) = (len(small), len(large))
		curr = [i for i in range(m + 1)]
		prev = [0 for i in range(m + 1)]
		for i in range(1, n + 1):
			(prev, curr) = (curr, prev)
			curr[0] = i
			for j in range(1, m + 1):
				if small[j - 1] == large[i - 1]:
					curr[j] = prev[j - 1]
				else:
					curr[j] = 1 + min(curr[j - 1], prev[j], prev[j - 1])
		return curr[-1]


class Solution:

	def editDistance(self, word1, word2):
		dp = [[float('inf')] * (len(word2) + 1) for i in range(len(word1) + 1)]
		for j in range(len(word2) + 1):
			dp[len(word1)][j] = len(word2) - j
		for i in range(len(word1) + 1):
			dp[i][len(word2)] = len(word1) - i
		for i in range(len(word1) - 1, -1, -1):
			for j in range(len(word2) - 1, -1, -1):
				if word1[i] == word2[j]:
					dp[i][j] = dp[i + 1][j + 1]
				else:
					dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])
		return dp[0][0]


class Solution:

	def editDistance(self, s, t):
		n = len(s)
		m = len(t)
		cache = [[float('inf')] * (m + 1) for i in range(n + 1)]
		for j in range(m + 1):
			cache[n][j] = m - j
		for i in range(n + 1):
			cache[i][m] = n - i
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if s[i] == t[j]:
					cache[i][j] = cache[i + 1][j + 1]
				else:
					cache[i][j] = 1 + min(cache[i + 1][j], cache[i][j + 1], cache[i + 1][j + 1])
		return cache[0][0]


import numpy as np

class Solution:

	def rec_sol(self, s, t, i, j):
		if i < 0 and j < 0:
			return 0
		if i < 0:
			return j + 1
		if j < 0:
			return i + 1
		if s[i] == t[j]:
			return self.rec_sol(s, t, i - 1, j - 1)
		else:
			return min(min(1 + self.rec_sol(s, t, i, j - 1), 1 + self.rec_sol(s, t, i - 1, j - 1)), 1 + self.rec_sol(s, t, i - 1, j))

	def dp_sol(self, s, t, i, j, dp):
		if i < 0 and j < 0:
			return 0
		if i < 0:
			return j + 1
		if j < 0:
			return i + 1
		if dp[i][j] != -1:
			return dp[i][j]
		if s[i] == t[j]:
			ans = self.dp_sol(s, t, i - 1, j - 1, dp)
		else:
			ans = min(min(1 + self.dp_sol(s, t, i, j - 1, dp), 1 + self.dp_sol(s, t, i - 1, j - 1, dp)), 1 + self.dp_sol(s, t, i - 1, j, dp))
		dp[i][j] = ans
		return ans

	def editDistance(self, s, t):
		len_s = len(s)
		len_t = len(t)
		dp = np.array([[-1] * (len_t + 1)] * (len_s + 1))
		for i in range(len_s + 1):
			for j in range(len_t + 1):
				if i == 0 and j == 0:
					dp[i][j] = 0
				elif i == 0:
					dp[i][j] = j
				elif j == 0:
					dp[i][j] = i
				elif s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(min(1 + dp[i][j - 1], 1 + dp[i - 1][j - 1]), 1 + dp[i - 1][j])
		return dp[len_s][len_t]


class Solution:
	INF = 34719347937

	def editDistance(self, s, t):
		dp = [[-1 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
		return self.editDis(s, t, dp)

	def editDis(self, s, t, dp):
		if dp[len(s)][len(t)] != -1:
			return dp[len(s)][len(t)]
		if len(t) == 0:
			return len(s)
		if len(s) == 0:
			return len(t)
		if s[-1] == t[-1]:
			dp[len(s)][len(t)] = self.editDis(s[:-1], t[:-1], dp)
			return dp[len(s)][len(t)]
		num_i = 1 + self.editDis(s, t[:-1], dp)
		num_rem = 1 + self.editDis(s[:-1], t, dp)
		num_rep = 1 + self.editDis(s[:-1], t[:-1], dp)
		dp[len(s)][len(t)] = min(num_i, num_rem, num_rep)
		return dp[len(s)][len(t)]


class Solution:

	def editDistance(self, s, t):
		l = [[0] * (len(s) + 1) for i in range(len(t) + 1)]
		for i in range(len(t) + 1):
			for j in range(len(s) + 1):
				if i == 0:
					l[i][j] = j
				elif j == 0:
					l[i][j] = i
				elif s[j - 1] == t[i - 1]:
					l[i][j] = l[i - 1][j - 1]
				elif s[j - 1] != t[i - 1]:
					l[i][j] = min(l[i][j - 1], l[i - 1][j], l[i - 1][j - 1]) + 1
		return l[-1][-1]


class Solution:

	def editDistance(self, s, t):
		n = len(s)
		m = len(t)
		temp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(1, m + 1):
			temp[0][i] = i
		for i in range(1, n + 1):
			temp[i][0] = i
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					temp[i][j] = temp[i - 1][j - 1]
				else:
					mn = min(temp[i - 1][j - 1], min(temp[i - 1][j], temp[i][j - 1]))
					temp[i][j] = 1 + mn
		return temp[n][m]


class Solution:

	def editDistance(self, str1, str2):
		m = len(str1)
		n = len(str2)
		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 - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
		return dp[m][n]


class Solution:

	def editDistance(self, s, t):

		def f(i, j, s, t, dp):
			if i < 0:
				return j + 1
			if j < 0:
				return i + 1
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i] == t[j]:
				dp[i][j] = f(i - 1, j - 1, s, t, dp)
				return dp[i][j]
			dp[i][j] = 1 + min(f(i - 1, j, s, t, dp), f(i, j - 1, s, t, dp), f(i - 1, j - 1, s, t, dp))
			return dp[i][j]
		dp = [[-1 for i in range(len(t))] for j in range(len(s))]
		return f(len(s) - 1, len(t) - 1, s, t, dp)


class Solution:

	def editDistance(self, s, t):
		matrix = list(([len(s) + len(t)] * (len(t) + 1) for i in range(len(s) + 1)))
		matrix[0][0] = 0
		for i in range(len(s)):
			matrix[i][0] = i
		for j in range(len(t)):
			matrix[0][j] = j
		for i in range(len(s)):
			for j in range(len(t)):
				m = float('inf')
				if s[i] == t[j]:
					m = min(m, matrix[i][j])
				else:
					m = min(m, matrix[i][j] + 1)
				m = min(m, matrix[i][j + 1] + 1)
				m = min(m, matrix[i + 1][j] + 1)
				matrix[i + 1][j + 1] = m
		return matrix[-1][-1]


class Solution:

	def editDistance(self, s, t):
		(a, b) = (len(s), len(t))
		dp = [[0] * (a + 1) for i in range(b + 1)]
		for i in range(a):
			dp[0][i + 1] = i + 1
		for i in range(b):
			dp[i + 1][0] = i + 1
		for i in range(1, b + 1):
			for j in range(1, a + 1):
				(x, y) = (i - 1, j - 1)
				if s[y] == t[x]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
		return dp[b][a]


class Solution:

	def computeEditDistance(s, t, dp):
		if (s, t) in dp:
			return dp[s, t]
		if len(s) == 0 or len(t) == 0:
			count = max(len(s), len(t))
			return count
		if s[-1] == t[-1]:
			return Solution.computeEditDistance(s[:-1], t[:-1], dp)
		else:
			countSub = Solution.computeEditDistance(s[:-1], t[:-1], dp) + 1
			countIns = Solution.computeEditDistance(s, t[:-1], dp) + 1
			countDel = Solution.computeEditDistance(s[:-1], t, dp) + 1
			count = min(countSub, countIns, countDel)
		dp[s, t] = count
		return count

	def editDistance(self, s, t):
		dp = {}
		return Solution.computeEditDistance(s, t, dp)


class Solution:

	def editDistance(self, s, t):
		dp = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]
		for j in range(len(t)):
			dp[len(s)][j] = len(t) - j
		for i in range(len(s)):
			dp[i][len(t)] = len(s) - i
		for i in range(len(s) - 1, -1, -1):
			for j in range(len(t) - 1, -1, -1):
				ans = 0
				if s[i] == t[j]:
					ans = dp[i + 1][j + 1]
				else:
					insertAns = 1 + dp[i][j + 1]
					deleteAns = 1 + dp[i + 1][j]
					replaceAns = 1 + dp[i + 1][j + 1]
					ans = min(insertAns, min(deleteAns, replaceAns))
				dp[i][j] = ans
		return dp[0][0]


class Solution:

	def editDistance(self, s, t):
		_n1 = len(s) + 1
		_n2 = len(t) + 1
		a = [[0 for i in range(_n2)] for j in range(_n1)]
		for i in range(_n2):
			a[0][i] = i
		for i in range(_n1):
			a[i][0] = i
		for i in range(1, _n1):
			for j in range(1, _n2):
				a[i][j] = a[i - 1][j - 1]
				if s[i - 1] != t[j - 1]:
					a[i][j] = min(a[i][j - 1], a[i - 1][j - 1], a[i - 1][j]) + 1
		return a[_n1 - 1][_n2 - 1]


from collections import defaultdict

class Solution:
	dp = defaultdict(lambda : defaultdict(lambda : -1))

	def recursion(self, s: str, t: str, m: int, n: int) -> int:
		if m == -1:
			return n + 1
		if n == -1:
			return m + 1
		if self.dp[m][n] == -1:
			if s[m] == t[n]:
				self.dp[m][n] = self.recursion(s, t, m - 1, n - 1)
			else:
				self.dp[m][n] = 1 + min(self.recursion(s, t, m, n - 1), self.recursion(s, t, m - 1, n), self.recursion(s, t, m - 1, n - 1))
		return self.dp[m][n]

	def editDistance(self, s, t):
		self.dp = defaultdict(lambda : defaultdict(lambda : -1))
		return self.recursion(s, t, len(s) - 1, len(t) - 1)


class Solution:

	def editDistance(self, s, t):
		x = len(s)
		y = len(t)
		dp = [[0] * (y + 1) for i in range(x + 1)]
		for i in range(0, x + 1):
			for j in range(0, y + 1):
				if i == 0:
					dp[i][j] = j
				elif j == 0:
					dp[i][j] = i
				elif s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					f1 = dp[i - 1][j - 1]
					f2 = dp[i - 1][j]
					f3 = dp[i][j - 1]
					dp[i][j] = 1 + min([f1, f2, f3])
		return dp[x][y]


class Solution:

	def editRun(self, i, j):
		if (i, j) in self.memo:
			return self.memo[i, j]
		if i < 0:
			return j + 1
		if j < 0:
			return i + 1
		if self.s[i] == self.t[j]:
			answer = self.editRun(i - 1, j - 1)
			self.memo[i, j] = answer
			return answer
		answer = 1 + min(self.editRun(i - 1, j - 1), self.editRun(i - 1, j), self.editRun(i, j - 1))
		self.memo[i, j] = answer
		return answer

	def editDistance(self, s, t):
		self.memo = {}
		self.s = s
		self.t = t
		return self.editRun(len(s) - 1, len(t) - 1)


class Solution:

	def solve(self, a, b, i, j):
		if i == len(a):
			return len(b) - j
		if j == len(b):
			return len(a) - i
		if a[i] == b[j]:
			return self.solve(a, b, i + 1, j + 1)
		else:
			insert = 1 + self.solve(a, b, i, j + 1)
			delete = 1 + self.solve(a, b, i + 1, j)
			replace = 1 + self.solve(a, b, i + 1, j + 1)
			return min(insert, delete, replace)

	def solve_memo(self, a, b, i, j, F):
		if i == len(a):
			return len(b) - j
		if j == len(b):
			return len(a) - i
		if F[i][j] != -1:
			return F[i][j]
		if a[i] == b[j]:
			return self.solve_memo(a, b, i + 1, j + 1, F)
		else:
			insert = 1 + self.solve_memo(a, b, i, j + 1, F)
			delete = 1 + self.solve_memo(a, b, i + 1, j, F)
			replace = 1 + self.solve_memo(a, b, i + 1, j + 1, F)
			F[i][j] = min(insert, delete, replace)
			return F[i][j]

	def solve_tab(self, s, t):
		F = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
		for j in range(len(t)):
			F[len(s)][j] = len(t) - j
		for i in range(len(s)):
			F[i][len(t)] = len(s) - i
		for i in range(len(s) - 1, -1, -1):
			for j in range(len(t) - 1, -1, -1):
				if s[i] == t[j]:
					F[i][j] = F[i + 1][j + 1]
				else:
					insert = 1 + F[i][j + 1]
					delete = 1 + F[i + 1][j]
					replace = 1 + F[i + 1][j + 1]
					F[i][j] = min(insert, delete, replace)
		return F[0][0]

	def solve_tab2(self, s, t):
		curr = [0 for _ in range(len(t) + 1)]
		nextt = [0 for _ in range(len(t) + 1)]
		for j in range(len(t) + 1):
			nextt[j] = len(t) - j
		for i in range(len(s) - 1, -1, -1):
			for j in range(len(t) - 1, -1, -1):
				curr[len(t)] = len(s) - i
				if s[i] == t[j]:
					curr[j] = nextt[j + 1]
				else:
					insert = 1 + curr[j + 1]
					delete = 1 + nextt[j]
					replace = 1 + nextt[j + 1]
					curr[j] = min(insert, delete, replace)
			nextt = curr[:]
		return nextt[0]

	def editDistance(self, s, t):
		return self.solve_tab2(s, t)


class Solution:

	def editDistance(self, s, t):
		stateMap = [[i for i in range(len(t) + 1)] for _ in range(len(s) + 1)]
		for i in range(1, len(s) + 1):
			stateMap[i][0] = i
		for i in range(1, len(t) + 1):
			stateMap[0][i] = i
		for r in range(1, len(s) + 1):
			for c in range(1, len(t) + 1):
				if s[r - 1] == t[c - 1]:
					stateMap[r][c] = stateMap[r - 1][c - 1]
				else:
					stateMap[r][c] = min(stateMap[r][c - 1], stateMap[r - 1][c], stateMap[r - 1][c - 1]) + 1
		return stateMap[len(s)][len(t)]


class Solution:

	def editDistance(self, s, t):
		dp = [[-1] * (len(t) + 1) for _ in range(len(s) + 1)]

		def op(s, t, i, j):
			if i == 0 and j == 0:
				return 0
			if i == 0 or j == 0:
				return max(i, j)
			if dp[i][j] != -1:
				return dp[i][j]
			if s[i - 1] == t[j - 1]:
				dp[i][j] = op(s, t, i - 1, j - 1)
				return dp[i][j]
			else:
				dp[i][j] = 1 + min(op(s, t, i - 1, j - 1), op(s, t, i, j - 1), op(s, t, i - 1, j))
				return dp[i][j]
		return op(s, t, len(s), len(t))


class Solution:
	dp = []
	count = 0

	def gen(self, x, y, s1, s2):
		if y == 0 or x == 0:
			return abs(x - y)
		if self.dp[x][y] != -1:
			return self.dp[x][y]
		p = 9999999
		if s1[x - 1] == s2[y - 1]:
			p = self.gen(x - 1, y - 1, s1, s2)
		l = self.gen(x - 1, y, s1, s2) + 1
		r = self.gen(x, y - 1, s1, s2) + 1
		g = self.gen(x - 1, y - 1, s1, s2) + 1
		self.dp[x][y] = min(p, l, r, g)
		return min(p, l, r, g)

	def editDistance(self, s, t):
		self.dp = []
		for i in range(len(s) + 1):
			b = []
			for j in range(len(t) + 1):
				b.append(-1)
			self.dp.append(b)
		return self.gen(len(s), len(t), s, t)


class Solution:

	def editRun(self, m, n, s, t):
		if (m, n) in self.memo:
			return self.memo[m, n]
		if n == 0:
			return m
		if m == 0:
			return n
		if s[m - 1] == t[n - 1]:
			self.memo[m, n] = self.editRun(m - 1, n - 1, s, t)
			return self.memo[m, n]
		else:
			self.memo[m, n] = 1 + min(self.editRun(m - 1, n, s, t), self.editRun(m, n - 1, s, t), self.editRun(m - 1, n - 1, s, t))
			return self.memo[m, n]

	def editDistance(self, s, t):
		self.memo = {}
		return self.editRun(len(s), len(t), s, t)


class Solution:

	def editDistance(self, s, t):
		ss = len(s) + 1
		ts = len(t) + 1
		m = [[0 for i in range(ts)] for j in range(ss)]
		m[0][0] = 0
		for i in range(1, ss):
			m[i][0] = m[i - 1][0] + 1
		for j in range(1, ts):
			m[0][j] = m[0][j - 1] + 1
		for i in range(1, ss):
			for j in range(1, ts):
				if s[i - 1] == t[j - 1]:
					m[i][j] = m[i - 1][j - 1]
				else:
					m[i][j] = min(m[i - 1][j - 1], min(m[i][j - 1], m[i - 1][j])) + 1
		return m[ss - 1][ts - 1]


class Solution:

	def editDistance(self, s, t):

		def edit_distance(s, t, i, j, dp):
			if i <= 0:
				return j
			if j <= 0:
				return i
			if dp[i - 1][j - 1] != -1:
				return dp[i - 1][j - 1]
			if s[i - 1] == t[j - 1]:
				dp[i - 1][j - 1] = edit_distance(s, t, i - 1, j - 1, dp)
				return dp[i - 1][j - 1]
			else:
				remove = edit_distance(s, t, i - 1, j, dp)
				replace = edit_distance(s, t, i - 1, j - 1, dp)
				insert = edit_distance(s, t, i, j - 1, dp)
				dp[i - 1][j - 1] = 1 + min(insert, replace, remove)
				return dp[i - 1][j - 1]
		dp = [[-1 for i in range(len(t))] for j in range(len(s))]
		res = edit_distance(s, t, len(s), len(t), dp)
		return res


import sys

class Solution:

	def editDistance(self, s, t):
		(n, m) = (len(s), len(t))
		dp = [[sys.maxsize for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(n + 1):
			dp[0][i] = i
		for i in range(m + 1):
			dp[i][0] = i
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if t[i - 1] == s[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = 1 + min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def editDistance(self, s, t):
		l1 = len(s)
		l2 = len(t)
		dp = [[float('inf') for _ in range(l2 + 1)] for _ in range(l1 + 1)]
		for i in range(l1 + 1):
			dp[i][0] = i
		for i in range(l2 + 1):
			dp[0][i] = i
		for i in range(l1):
			for j in range(l2):
				if s[i] == t[j]:
					dp[i + 1][j + 1] = dp[i][j]
				else:
					dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[i + 1][j] + 1, dp[i][j] + 1)
		return dp[-1][-1]