






class      __a    :







 def __init__(						self   :  Optional[int]		):


      '''simple docstring'''






      UpperCamelCase__     :  List[Any]										=    ""
      UpperCamelCase__     :  List[Any]										=    ""
      UpperCamelCase__     :  Tuple										=    []







 def    __lowercase   (						self   :  List[Any]				,  SCREAMING_SNAKE_CASE   :  Union[str, Any]				,  SCREAMING_SNAKE_CASE   :  str		):


      '''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]:
                UpperCamelCase__     :  Union[str, Any]										=    self.__min_dist_top_down_dp(m - 1				,  n - 1		)
           else:
                UpperCamelCase__     :  Dict										=    self.__min_dist_top_down_dp(SCREAMING_SNAKE_CASE				,  n - 1		)
                UpperCamelCase__     :  Dict										=    self.__min_dist_top_down_dp(m - 1				,  SCREAMING_SNAKE_CASE		)
                UpperCamelCase__     :  str										=    self.__min_dist_top_down_dp(m - 1				,  n - 1		)
                UpperCamelCase__     :  Tuple										=    1 + min(SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE		)

           return self.dp[m][n]







 def    __lowercase   (						self   :  Optional[int]				,  SCREAMING_SNAKE_CASE   :  str				,  SCREAMING_SNAKE_CASE   :  List[str]		):


      '''simple docstring'''






      UpperCamelCase__     :  Dict										=    worda
      UpperCamelCase__     :  List[Any]										=    worda
      UpperCamelCase__     :  int										=    [[-1 for _ in range(len(SCREAMING_SNAKE_CASE		)		)] for _ in range(len(SCREAMING_SNAKE_CASE		)		)]

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







 def    __lowercase   (						self   :  Optional[Any]				,  SCREAMING_SNAKE_CASE   :  Dict				,  SCREAMING_SNAKE_CASE   :  Any		):


      '''simple docstring'''






      UpperCamelCase__     :  Optional[int]										=    worda
      UpperCamelCase__     :  str										=    worda
      UpperCamelCase__     :  Optional[int]										=    len(SCREAMING_SNAKE_CASE		)
      UpperCamelCase__     :  List[Any]										=    len(SCREAMING_SNAKE_CASE		)
      UpperCamelCase__     :  int										=    [[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
                     UpperCamelCase__     :  Tuple										=    j
                elif j == 0:  # second string is empty
                     UpperCamelCase__     :  Tuple										=    i
                elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                     UpperCamelCase__     :  Any										=    self.dp[i - 1][j - 1]
                else:
                     UpperCamelCase__     :  Optional[int]										=    self.dp[i][j - 1]
                     UpperCamelCase__     :  Dict										=    self.dp[i - 1][j]
                     UpperCamelCase__     :  Dict										=    self.dp[i - 1][j - 1]
                     UpperCamelCase__     :  int										=    1 + min(SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE		)
      return self.dp[m][n]


if __name__ == "__main__":
 lowerCamelCase      :				Optional[int]							=EditDistance()

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

 lowerCamelCase      :				Union[str, Any]							=input('''Enter the first string: ''').strip()
 lowerCamelCase      :				Dict							=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 ***************''')







import numpy as np





def 		__UpperCAmelCase     (	a_):
							return 1 / (1 + np.exp(-vector))


if __name__ == "__main__":
	import doctest

	doctest.testmod()





