def levenshtein_distance(a: str, b: str) -> int:
    """
    Calculates the levenhstein distance between to two given strings. The levenshtein distance is a string metric
    used for measuring the difference between two given strings. It is the minimum number of single character edits
    (insert, remove or replace) required to change one word into the other word.

    :param a: the first string
    :param b: the second string
    :return: the levensthein distance between the two given strings
    """

    lookup_table = [[0 for a_index in range(len(a) + 1)] for b_index in range(len(b) + 1)]

    for a_index in range(0, len(a) + 1):
        for b_index in range(0, len(b) + 1):
            if a_index == 0:  # a string is empty
                lookup_table[b_index][a_index] = b_index
            elif b_index == 0:  # b string is empty
                lookup_table[b_index][a_index] = a_index
            else:
                if a[a_index - 1] == b[b_index - 1]:  # both string already have the same character at the given index
                    lookup_table[b_index][a_index] = lookup_table[b_index - 1][a_index - 1]
                else:
                    lookup_table[b_index][a_index] = 1 + \
                                                     min(lookup_table[b_index - 1][a_index - 1],  # replace character
                                                         lookup_table[b_index - 1][a_index],  # remove character
                                                         lookup_table[b_index][a_index - 1])  # insert character

    return lookup_table[len(b)][len(a)]