


from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

snake_case__				:	Optional[Any]					       =					TypeVar('KEY')
snake_case__				:	Any					       =					TypeVar('VAL')





@dataclass(frozen=a__						,       slots=a__						)
class   SCREAMING_SNAKE_CASE_			(Generic[KEY, VAL]						):




       '''simple docstring'''



       _a   							=							42
       _a   							=							42







class   SCREAMING_SNAKE_CASE_			(_Item						):




       '''simple docstring'''



       def __init__(						self				:				List[str]							)					->None:
          super().__init__(__a		,				__a							)




       def __bool__(						self				:				Tuple							)					->bool:
          return False







snake_case__				:	List[str]					       =					_DeletedItem()





class   SCREAMING_SNAKE_CASE_			(MutableMapping[KEY, VAL]						):




       '''simple docstring'''



       def __init__(						self				:				int		,				__a				:				int = 8		,				__a				:				float = 0.75							)					->None:
          lowerCamelCase_						:   List[str]		= initial_block_size
          lowerCamelCase_						:   list[_Item | None]		= [None] * initial_block_size
          assert 0.0 < capacity_factor < 1.0
          lowerCamelCase_						:   List[str]		= capacity_factor
          lowerCamelCase_						:   Tuple		= 0



       def 				_lowerCAmelCase							(						self				:				Optional[Any]		,				__a				:				KEY							)					->int:
          return hash(__a							) % len(self._buckets							)



       def 				_lowerCAmelCase							(						self				:				str		,				__a				:				int							)					->int:
          return (ind + 1) % len(self._buckets							)



       def 				_lowerCAmelCase							(						self				:				List[str]		,				__a				:				int		,				__a				:				KEY		,				__a				:				VAL							)					->bool:
          lowerCamelCase_						:   str		= self._buckets[ind]
          if not stored:
             lowerCamelCase_						:   Optional[int]		= _Item(__a		,				__a							)
             self._len += 1
             return True
          elif stored.key == key:
             lowerCamelCase_						:   List[str]		= _Item(__a		,				__a							)
             return True
          else:
             return False



       def 				_lowerCAmelCase							(						self				:				Optional[int]							)					->bool:
          lowerCamelCase_						:   Optional[int]		= len(self._buckets							) * self._capacity_factor
          return len(self							) >= int(__a							)



       def 				_lowerCAmelCase							(						self				:				Optional[int]							)					->bool:
          if len(self._buckets							) <= self._initial_block_size:
             return False
          lowerCamelCase_						:   Dict		= len(self._buckets							) * self._capacity_factor / 2
          return len(self							) < limit



       def 				_lowerCAmelCase							(						self				:				Optional[Any]		,				__a				:				int							)					->None:
          lowerCamelCase_						:   Optional[Any]		= self._buckets
          lowerCamelCase_						:   Any		= [None] * new_size
          lowerCamelCase_						:   int		= 0
          for item in old_buckets:
             if item:
                self._add_item(item.key		,				item.val							)



       def 				_lowerCAmelCase							(						self				:				List[str]							)					->None:
          self._resize(len(self._buckets							) * 2							)



       def 				_lowerCAmelCase							(						self				:				Tuple							)					->None:
          self._resize(len(self._buckets							) // 2							)



       def 				_lowerCAmelCase							(						self				:				Union[str, Any]		,				__a				:				KEY							)					->Iterator[int]:
          lowerCamelCase_						:   Dict		= self._get_bucket_index(__a							)
          for _ in range(len(self._buckets							)							):
             yield ind
             lowerCamelCase_						:   Dict		= self._get_next_ind(__a							)



       def 				_lowerCAmelCase							(						self				:				str		,				__a				:				KEY		,				__a				:				VAL							)					->None:
          for ind in self._iterate_buckets(__a							):
             if self._try_set(__a		,				__a		,				__a							):
                break



       def __setitem__(						self				:				int		,				__a				:				KEY		,				__a				:				VAL							)					->None:
          if self._is_full():
             self._size_up()

          self._add_item(__a		,				__a							)



       def __delitem__(						self				:				Tuple		,				__a				:				KEY							)					->None:
          for ind in self._iterate_buckets(__a							):
             lowerCamelCase_						:   str		= self._buckets[ind]
             if item is None:
                raise KeyError(__a							)
             if item is _deleted:
                continue
             if item.key == key:
                lowerCamelCase_						:   Optional[int]		= _deleted
                self._len -= 1
                break
          if self._is_sparse():
             self._size_down()



       def __getitem__(						self				:				str		,				__a				:				KEY							)					->VAL:
          for ind in self._iterate_buckets(__a							):
             lowerCamelCase_						:   Optional[int]		= self._buckets[ind]
             if item is None:
                break
             if item is _deleted:
                continue
             if item.key == key:
                return item.val
          raise KeyError(__a							)



       def __len__(						self				:				Tuple							)					->int:
          return self._len



       def __iter__(						self				:				List[Any]							)					->Iterator[KEY]:
          yield from (item.key for item in self._buckets if item)




       def __repr__(						self				:				Dict							)					->str:
          lowerCamelCase_						:   str		= """ ,""".join(
              F'''{item.key}: {item.val}''' for item in self._buckets if item							)
          return F'''HashMap({val_string})'''









class   SCREAMING_SNAKE_CASE_			:




       '''simple docstring'''



       def __init__(						self				:				List[Any]							)					->Tuple:
          lowerCamelCase_						:   Optional[Any]		= """"""
          lowerCamelCase_						:   Dict		= """"""
          lowerCamelCase_						:   Optional[Any]		= []



       def 				_lowerCAmelCase							(						self				:				Optional[Any]		,				__a				:				int		,				__a				:				int							)					->int:
          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_						:   Optional[Any]		= self.__min_dist_top_down_dp(m - 1		,				n - 1							)
             else:
                lowerCamelCase_						:   List[Any]		= self.__min_dist_top_down_dp(__a		,				n - 1							)
                lowerCamelCase_						:   Union[str, Any]		= self.__min_dist_top_down_dp(m - 1		,				__a							)
                lowerCamelCase_						:   Any		= self.__min_dist_top_down_dp(m - 1		,				n - 1							)
                lowerCamelCase_						:   Tuple		= 1 + min(__a		,				__a		,				__a							)

             return self.dp[m][n]



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


if __name__ == "__main__":
      snake_case__				:	Optional[Any]					       =					EditDistance()

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

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





