




'''simple docstring'''





import functools





def      __a     (       _UpperCamelCase:   str ,						_UpperCamelCase:   str   )						->			int:

     """simple docstring"""




     _snake_case							=				len(_UpperCamelCase   )
     _snake_case							=				len(_UpperCamelCase   )

     @functools.cache
     def min_distance(_UpperCamelCase:   int ,						_UpperCamelCase:   int   ) -> int:
          # if first word index is overflow - delete all from the second word
          if indexa >= len_worda:
               return len_worda - indexa
          # if second word index is overflow - delete all from the first word
          if indexa >= len_worda:
               return len_worda - indexa
          _snake_case							=				int(worda[indexa] != worda[indexa]   )  # current letters not identical
          return min(
              1 + min_distance(indexa + 1 ,						_UpperCamelCase   ) ,						1 + min_distance(_UpperCamelCase ,						indexa + 1   ) ,						diff + min_distance(indexa + 1 ,						indexa + 1   ) ,						)

     return min_distance(0 ,						0   )


if __name__ == "__main__":
   import doctest

   doctest.testmod()








'''simple docstring'''





from __future__ import annotations

from typing import Any





def      __a     (       _UpperCamelCase:   list[Any]   )						->			None:

     """simple docstring"""




     create_state_space_tree(_UpperCamelCase ,						[] ,						0   )





def      __a     (       _UpperCamelCase:   list[Any] ,						_UpperCamelCase:   list[Any] ,						_UpperCamelCase:   int   )						->			None:

     """simple docstring"""




     if index == len(_UpperCamelCase   ):
          print(_UpperCamelCase   )
          return

     create_state_space_tree(_UpperCamelCase ,						_UpperCamelCase ,						index + 1   )
     current_subsequence.append(sequence[index]   )
     create_state_space_tree(_UpperCamelCase ,						_UpperCamelCase ,						index + 1   )
     current_subsequence.pop()


if __name__ == "__main__":
   UpperCamelCase_						:      list[Any]       =						[3, 1, 2, 4]
   generate_all_subsequences(seq)

   seq.clear()
   seq.extend(['''A''', '''B''', '''C'''])
   generate_all_subsequences(seq)


