





class SCREAMING_SNAKE_CASE_						:






						def __init__(      self      :      Union[str, Any]	)							->    Dict:







							"""simple docstring"""


							snake_case_		:			Dict											=	''
							snake_case_		:			List[str]											=	''
							snake_case_		:			Union[str, Any]											=	[]






						def UpperCAmelCase_				(      self      :      Union[str, Any]		,   _A      :      int		,   _A      :      int	)							->    int:







							"""simple docstring"""


							if m == -1:
								return n + 1
							elif n == -1:
								return m + 1
							elif self.dp[m][n] > -1:
								return self.dp[m][n]
							else:
								if self.worda[m] == self.worda[n]:
									snake_case_		:			Dict											=	self.__min_dist_top_down_dp(m - 1		,   n - 1	)
								else:
									snake_case_		:			str											=	self.__min_dist_top_down_dp(_A		,   n - 1	)
									snake_case_		:			int											=	self.__min_dist_top_down_dp(m - 1		,   _A	)
									snake_case_		:			Optional[Any]											=	self.__min_dist_top_down_dp(m - 1		,   n - 1	)
									snake_case_		:			List[str]											=	1 + min(_A		,   _A		,   _A	)

								return self.dp[m][n]






						def UpperCAmelCase_				(      self      :      str		,   _A      :      str		,   _A      :      str	)							->    int:







							"""simple docstring"""


							snake_case_		:			Optional[int]											=	worda
							snake_case_		:			Union[str, Any]											=	worda
							snake_case_		:			int											=	[[-1 for _ in range(len(_A	)	)] for _ in range(len(_A	)	)]

							return self.__min_dist_top_down_dp(len(_A	) - 1		,   len(_A	) - 1	)






						def UpperCAmelCase_				(      self      :      Optional[Any]		,   _A      :      str		,   _A      :      str	)							->    int:







							"""simple docstring"""


							snake_case_		:			Optional[Any]											=	worda
							snake_case_		:			List[str]											=	worda
							snake_case_		:			Tuple											=	len(_A	)
							snake_case_		:			str											=	len(_A	)
							snake_case_		:			Union[str, Any]											=	[[0 for _ in range(n + 1	)] for _ in range(m + 1	)]

							for i in range(m + 1	):
								for j in range(n + 1	):
									if i == 0:  # first string is empty
										snake_case_		:			Optional[int]											=	j
									elif j == 0:  # second string is empty
										snake_case_		:			Dict											=	i
									elif worda[i - 1] == worda[j - 1]:  # last characters are equal
										snake_case_		:			Any											=	self.dp[i - 1][j - 1]
									else:
										snake_case_		:			Optional[Any]											=	self.dp[i][j - 1]
										snake_case_		:			Optional[int]											=	self.dp[i - 1][j]
										snake_case_		:			Union[str, Any]											=	self.dp[i - 1][j - 1]
										snake_case_		:			List[Any]											=	1 + min(_A		,   _A		,   _A	)
							return self.dp[m][n]


if __name__ == "__main__":
						_SCREAMING_SNAKE_CASE      	=		EditDistance()

						print("""****************** Testing Edit Distance DP Algorithm ******************""")
						print()

						_SCREAMING_SNAKE_CASE      	=		input("""Enter the first string: """).strip()
						_SCREAMING_SNAKE_CASE      	=		input("""Enter the second string: """).strip()

						print()
						print(F'''The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}''')
						print(F'''The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}''')
						print()
						print("""*************** End of Testing Edit Distance DP Algorithm ***************""")








from ....utils import logging


_SCREAMING_SNAKE_CASE      	=		logging.get_logger(__name__)
class SCREAMING_SNAKE_CASE_						(					snake_case_					):






						def __init__(      self      :      str		,   _A      :      List[Any]		,   _A      :      List[Any]=None		,   _A      :      str=2048	)							->    Optional[int]:







							"""simple docstring"""


							snake_case_		:			Tuple											=	config.__dict__
							snake_case_		:			List[str]											=	modal_hidden_size
							if num_labels:
								snake_case_		:			int											=	num_labels

