
from __future__ import annotations







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    if not list_of_ints:
        return []

    if min(a__   ) < 0:
        raise ValueError('''All numbers must be positive'''   )

    SCREAMING_SNAKE_CASE				:				Tuple				      = max(len(bin(a__   )[2:]   ) for x in list_of_ints   )
    return _msd_radix_sort(a__ ,						a__   )







def 				UpperCAmelCase_(    a__ ,						a__   ):



    """simple docstring"""



    if bit_position == 0 or len(a__   ) in [0, 1]:
        return list_of_ints

    SCREAMING_SNAKE_CASE				:				Optional[int]				      = []
    SCREAMING_SNAKE_CASE				:				Optional[int]				      = []
    # Split numbers based on bit at bit_position from the right
    for number in list_of_ints:
        if (number >> (bit_position - 1)) & 1:
            # number has a one at bit bit_position
            ones.append(a__   )
        else:
            # number has a zero at bit bit_position
            zeros.append(a__   )

    # recursively split both lists further
    SCREAMING_SNAKE_CASE				:				Optional[Any]				      = _msd_radix_sort(a__ ,						bit_position - 1   )
    SCREAMING_SNAKE_CASE				:				List[str]				      = _msd_radix_sort(a__ ,						bit_position - 1   )

    # recombine lists
    SCREAMING_SNAKE_CASE				:				Optional[Any]				      = zeros
    res.extend(a__   )

    return res







def 				UpperCAmelCase_(    a__   ):



    """simple docstring"""



    SCREAMING_SNAKE_CASE				:				List[Any]				      = len(a__   )
    if not list_of_ints or length == 1:
        return

    if min(a__   ) < 0:
        raise ValueError('''All numbers must be positive'''   )

    SCREAMING_SNAKE_CASE				:				Optional[Any]				      = max(len(bin(a__   )[2:]   ) for x in list_of_ints   )
    _msd_radix_sort_inplace(a__ ,						a__ ,						0 ,						a__   )







def 				UpperCAmelCase_(    a__ ,						a__ ,						a__ ,						a__   ):



    """simple docstring"""



    if bit_position == 0 or end_index - begin_index <= 1:
        return

    bit_position -= 1

    SCREAMING_SNAKE_CASE				:				Tuple				      = begin_index
    SCREAMING_SNAKE_CASE				:				str				      = end_index - 1
    while i <= j:
        SCREAMING_SNAKE_CASE				:				str				      = False
        if not (list_of_ints[i] >> bit_position) & 1:
            # found zero at the beginning
            i += 1
            SCREAMING_SNAKE_CASE				:				Any				      = True
        if (list_of_ints[j] >> bit_position) & 1:
            # found one at the end
            j -= 1
            SCREAMING_SNAKE_CASE				:				Tuple				      = True

        if changed:
            continue

        SCREAMING_SNAKE_CASE				:				int				      = list_of_ints[j], list_of_ints[i]
        j -= 1
        if j != i:
            i += 1

    _msd_radix_sort_inplace(a__ ,						a__ ,						a__ ,						a__   )
    _msd_radix_sort_inplace(a__ ,						a__ ,						a__ ,						a__   )


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}')




