


"""simple docstring"""
class        __A       :





							'''simple docstring'''

							def __init__(			self							: List[str]    )   ->Optional[int]:



														"""simple docstring"""



														snake_case_          =						""""""
														snake_case_          =						""""""
														snake_case_          =						[]



							def 						lowerCAmelCase    (			self							: Union[str, Any]						,    UpperCAmelCase_							: int						,    UpperCAmelCase_							: 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_          =						self.__min_dist_top_down_dp(m - 1						,    n - 1    )
																					else:
																												snake_case_          =						self.__min_dist_top_down_dp(UpperCAmelCase_						,    n - 1    )
																												snake_case_          =						self.__min_dist_top_down_dp(m - 1						,    UpperCAmelCase_    )
																												snake_case_          =						self.__min_dist_top_down_dp(m - 1						,    n - 1    )
																												snake_case_          =						1 + min(UpperCAmelCase_						,    UpperCAmelCase_						,    UpperCAmelCase_    )

																					return self.dp[m][n]



							def 						lowerCAmelCase    (			self							: Any						,    UpperCAmelCase_							: str						,    UpperCAmelCase_							: str    )   ->int:



														"""simple docstring"""



														snake_case_          =						worda
														snake_case_          =						worda
														snake_case_          =						[[-1 for _ in range(len(UpperCAmelCase_    )    )] for _ in range(len(UpperCAmelCase_    )    )]

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



							def 						lowerCAmelCase    (			self							: Dict						,    UpperCAmelCase_							: str						,    UpperCAmelCase_							: str    )   ->int:



														"""simple docstring"""



														snake_case_          =						worda
														snake_case_          =						worda
														snake_case_          =						len(UpperCAmelCase_    )
														snake_case_          =						len(UpperCAmelCase_    )
														snake_case_          =						[[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_          =						j
																												elif j == 0:  # second string is empty
																																			snake_case_          =						i
																												elif worda[i - 1] == worda[j - 1]:  # last characters are equal
																																			snake_case_          =						self.dp[i - 1][j - 1]
																												else:
																																			snake_case_          =						self.dp[i][j - 1]
																																			snake_case_          =						self.dp[i - 1][j]
																																			snake_case_          =						self.dp[i - 1][j - 1]
																																			snake_case_          =						1 + min(UpperCAmelCase_						,    UpperCAmelCase_						,    UpperCAmelCase_    )
														return self.dp[m][n]


if __name__ == "__main__":
				__SCREAMING_SNAKE_CASE							:      Union[str, Any]						=      EditDistance()

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

				__SCREAMING_SNAKE_CASE							:      Dict						=      input('Enter the first string: ').strip()
				__SCREAMING_SNAKE_CASE							:      str						=      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 ***************')










"""simple docstring"""
from __future__ import annotations

from collections.abc import Iterator





class        __A       :





							'''simple docstring'''

							def __init__(			self							: Any						,    UpperCAmelCase_							: int    )   ->None:



														"""simple docstring"""



														snake_case_          =						value
														snake_case_          =						None
														snake_case_          =						None





class        __A       :





							'''simple docstring'''

							def __init__(			self							: List[Any]						,    UpperCAmelCase_							: Node    )   ->None:



														"""simple docstring"""



														snake_case_          =						tree



							def 						lowerCAmelCase    (			self							: List[str]						,    UpperCAmelCase_							: Node | None    )   ->int:



														"""simple docstring"""



														if node is None:
																					return 0
														return node.value + (
														    self.depth_first_search(node.left    ) + self.depth_first_search(node.right    )
														)



							def __iter__(			self							: str    )   ->Iterator[int]:



														"""simple docstring"""



														yield self.depth_first_search(self.tree    )


if __name__ == "__main__":
				import doctest

				doctest.testmod()



