




'''simple docstring'''






from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

lowercase						:   List[Any]      						=							TypeVar('''T''')
lowercase						:   Dict      						=							TypeVar('''U''')

class 	SCREAMING_SNAKE_CASE_		(							Generic[T, U]					):



 def __init__(	self ,		A ,		A			):






        '''simple docstring'''




        lowercase	:		int    =   key
        lowercase	:		List[str]    =   val
        lowercase	:		int    =   0
        lowercase	:		DoubleLinkedListNode[T, U] | None    =   None
        lowercase	:		DoubleLinkedListNode[T, U] | None    =   None





 def __repr__(	self			):






        '''simple docstring'''




        return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
            self.key ,		self.val ,		self.freq ,		self.next is not None ,		self.prev is not None			)






class 	SCREAMING_SNAKE_CASE_		(							Generic[T, U]					):



 def __init__(	self			):






        '''simple docstring'''




        lowercase	:		DoubleLinkedListNode[T, U]    =   DoubleLinkedListNode(A ,		A			)
        lowercase	:		DoubleLinkedListNode[T, U]    =   DoubleLinkedListNode(A ,		A			)
        lowercase,  lowercase	:		Optional[int]    =   self.rear, self.head



 def __repr__(	self			):






        '''simple docstring'''




        lowercase	:		Tuple    =   ['''DoubleLinkedList''']
        lowercase	:		int    =   self.head
        while node.next is not None:
               rep.append(str(A			)			)
               lowercase	:		List[Any]    =   node.next
        rep.append(str(self.rear			)			)
        return ",\n    ".join(A			)



 def  SCREAMING_SNAKE_CASE(	self ,		A			):






        '''simple docstring'''




        lowercase	:		List[str]    =   self.rear.prev

        # All nodes other than self.head are guaranteed to have non-None previous
        assert previous is not None

        lowercase	:		int    =   node
        lowercase	:		Optional[int]    =   previous
        lowercase	:		List[str]    =   node
        lowercase	:		Tuple    =   self.rear
        node.freq += 1
        self._position_node(A			)



 def  SCREAMING_SNAKE_CASE(	self ,		A			):






        '''simple docstring'''




        while node.prev is not None and node.prev.freq > node.freq:
               # swap node with previous node
               lowercase	:		Optional[int]    =   node.prev

               lowercase	:		Dict    =   previous_node.prev
               lowercase	:		List[Any]    =   node.prev
               lowercase	:		Optional[int]    =   previous_node
               lowercase	:		List[str]    =   node





 def  SCREAMING_SNAKE_CASE(	self ,		A			):






        '''simple docstring'''




        if node.prev is None or node.next is None:
               return None

        lowercase	:		Optional[Any]    =   node.next
        lowercase	:		str    =   node.prev
        lowercase	:		str    =   None
        lowercase	:		List[str]    =   None
        return node






class 	SCREAMING_SNAKE_CASE_		(							Generic[T, U]					):
 __snake_case						:  dict[Callable[[T], U], LFUCache[T, U]]       =   {}



 def __init__(	self ,		A			):






        '''simple docstring'''




        lowercase	:		DoubleLinkedList[T, U]    =   DoubleLinkedList()
        lowercase	:		Optional[Any]    =   capacity
        lowercase	:		str    =   0
        lowercase	:		Any    =   0
        lowercase	:		Optional[Any]    =   0
        lowercase	:		dict[T, DoubleLinkedListNode[T, U]]    =   {}



 def __repr__(	self			):






        '''simple docstring'''




        return (
            f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
            f"""capacity={self.capacity}, current_size={self.num_keys})"""
        )



 def __contains__(	self ,		A			):






        '''simple docstring'''




        return key in self.cache



 def  SCREAMING_SNAKE_CASE(	self ,		A			):






        '''simple docstring'''




        if key in self.cache:
               self.hits += 1
               lowercase	:		DoubleLinkedListNode[T, U]    =   self.cache[key]
               lowercase	:		str    =   self.list.remove(self.cache[key]			)
               assert node == value_node

               # node is guaranteed not None because it is in self.cache
               assert node is not None
               self.list.add(A			)
               return node.val
        self.miss += 1
        return None



 def  SCREAMING_SNAKE_CASE(	self ,		A ,		A			):






        '''simple docstring'''




        if key not in self.cache:
               if self.num_keys >= self.capacity:
                      # delete first node when over capacity
                      lowercase	:		List[Any]    =   self.list.head.next

                      # guaranteed to have a non-None first node when num_keys > 0
                      # explain to type checker via assertions
                      assert first_node is not None
                      assert first_node.key is not None
                      assert self.list.remove(A			) is not None
                      # first_node guaranteed to be in list

                      del self.cache[first_node.key]
                      self.num_keys -= 1
               lowercase	:		Tuple    =   DoubleLinkedListNode(A ,		A			)
               self.list.add(self.cache[key]			)
               self.num_keys += 1

        else:
               lowercase	:		Tuple    =   self.list.remove(self.cache[key]			)
               assert node is not None  # node guaranteed to be in list
               lowercase	:		Optional[int]    =   value
               self.list.add(A			)





 @classmethod
 def  SCREAMING_SNAKE_CASE(	cls ,		A = 128			):






        '''simple docstring'''




        def cache_decorator_inner(A			) -> Callable[..., U]:
               def cache_decorator_wrapper(*A			) -> U:
                      if func not in cls.decorator_function_to_instance_map:
                             lowercase	:		Union[str, Any]    =   LFUCache(A			)

                      lowercase	:		Any    =   cls.decorator_function_to_instance_map[func].get(args[0]			)
                      if result is None:
                             lowercase	:		Optional[Any]    =   func(*A			)
                             cls.decorator_function_to_instance_map[func].put(args[0] ,		A			)
                      return result

               def cache_info() -> LFUCache[T, U]:
                      return cls.decorator_function_to_instance_map[func]

               setattr(A ,		'''cache_info''' ,		A			)  # noqa: B010

               return cache_decorator_wrapper

        return cache_decorator_inner


if __name__ == "__main__":
      import doctest

      doctest.testmod()










'''simple docstring'''






def 		a_(			lowerCamelCase ,					lowerCamelCase   )					->int:






       '''simple docstring'''




       if len(lowerCamelCase   ) < len(lowerCamelCase   ):
              return levenshtein_distance(lowerCamelCase ,					lowerCamelCase   )

       if len(lowerCamelCase   ) == 0:
              return len(lowerCamelCase   )

       lowercase	:		List[Any]    =   list(range(len(lowerCamelCase   ) + 1   )   )

       for i, ca in enumerate(lowerCamelCase   ):
              lowercase	:		Any    =   [i + 1]

              for j, ca in enumerate(lowerCamelCase   ):
                     # Calculate insertions, deletions and substitutions
                     lowercase	:		List[Any]    =   previous_row[j + 1] + 1
                     lowercase	:		str    =   current_row[j] + 1
                     lowercase	:		List[Any]    =   previous_row[j] + (ca != ca)

                     # Get the minimum to append to the current row
                     current_row.append(min(lowerCamelCase ,					lowerCamelCase ,					lowerCamelCase   )   )

              # Store the previous row
              lowercase	:		List[str]    =   current_row

       # Returns the last element (distance)
       return previous_row[-1]


if __name__ == "__main__":
      lowercase						:   Dict      						=							input('''Enter the first word:\n''').strip()
      lowercase						:   Tuple      						=							input('''Enter the second word:\n''').strip()

      lowercase						:   Tuple      						=							levenshtein_distance(first_word, second_word)
      print(f'Levenshtein distance between {first_word} and {second_word} is {result}')




