
"""simple docstring"""


class  __lowerCamelCase  :




				def __init__(				self   ):
							lowerCamelCase_					=  ''''''
							lowerCamelCase_					=  ''''''
							lowerCamelCase_					=  []




				def        UpperCAmelCase__						(				self							,						UpperCAmelCase							,						UpperCAmelCase   ):
							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]:
													lowerCamelCase_					=  self.__min_dist_top_down_dp(m - 1							,						n - 1   )
										else:
													lowerCamelCase_					=  self.__min_dist_top_down_dp(UpperCAmelCase							,						n - 1   )
													lowerCamelCase_					=  self.__min_dist_top_down_dp(m - 1							,						UpperCAmelCase   )
													lowerCamelCase_					=  self.__min_dist_top_down_dp(m - 1							,						n - 1   )
													lowerCamelCase_					=  1 + min(UpperCAmelCase							,						UpperCAmelCase							,						UpperCAmelCase   )

										return self.dp[m][n]




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


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

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

						A_    							=					input("""Enter the first string: """).strip()
						A_    							=					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 collections import namedtuple

a_					=     namedtuple("""from_to""", """from_ to""")

a_					=     {
    """cubicmeter""": from_to(1, 1),
    """litre""": from_to(0.001, 1000),
    """kilolitre""": from_to(1, 1),
    """gallon""": from_to(0.00454, 264.172),
    """cubicyard""": from_to(0.76455, 1.30795),
    """cubicfoot""": from_to(0.028, 35.3147),
    """cup""": from_to(0.000236588, 4226.75),
}







def 						__lowercase	(  snake_case_    :    float							,snake_case_    :    str							,snake_case_    :    str		)  ->float:



    '''simple docstring'''







    if from_type not in METRIC_CONVERSION:
        raise ValueError(
            F"""Invalid 'from_type' value: {from_type!r}  Supported values are:\n"""
            + ''', '''.join(snake_case_		)		)
    if to_type not in METRIC_CONVERSION:
        raise ValueError(
            F"""Invalid 'to_type' value: {to_type!r}.  Supported values are:\n"""
            + ''', '''.join(snake_case_		)		)
    return value * METRIC_CONVERSION[from_type].from_ * METRIC_CONVERSION[to_type].to


if __name__ == "__main__":
       import doctest

       doctest.testmod()




