Returns the Levenshtein Distance between two strings, `s1` and `s2` as an
    integer.

    http://en.wikipedia.org/wiki/Levenshtein_distance
    The Levenshtein Distance (aka edit distance) is how many changes (i.e.
    insertions, deletions, substitutions) have to be made to convert one
    string into another.

    For example, the Levenshtein distance between "kitten" and "sitting" is
    3, since the following three edits change one into the other, and there
    is no way to do it with fewer than three edits:
      kitten -> sitten -> sittin -> sitting

def levenshteinDistance(s1, s2):
    """
    Returns the Levenshtein Distance between two strings, `s1` and `s2` as an
    integer.

    http://en.wikipedia.org/wiki/Levenshtein_distance
    The Levenshtein Distance (aka edit distance) is how many changes (i.e.
    insertions, deletions, substitutions) have to be made to convert one
    string into another.

    For example, the Levenshtein distance between "kitten" and "sitting" is
    3, since the following three edits change one into the other, and there
    is no way to do it with fewer than three edits:
      kitten -> sitten -> sittin -> sitting
    """
    singleLetterMapping = {DOWNLEFT: '1', DOWN:'2', DOWNRIGHT:'3',
                           LEFT:'4', RIGHT:'6',
                           UPLEFT:'7', UP:'8', UPRIGHT:'9'}

    len1 = len([singleLetterMapping[letter] for letter in s1])
    len2 = len([singleLetterMapping[letter] for letter in s2])

    matrix = list(range(len1 + 1)) * (len2 + 1)
    for i in range(len2 + 1):
        matrix[i] = list(range(i, i + len1 + 1))
    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                matrix[i+1][j+1] = min(matrix[i+1][j] + 1, matrix[i][j+1] + 1, matrix[i][j])
            else:
                matrix[i+1][j+1] = min(matrix[i+1][j] + 1, matrix[i][j+1] + 1, matrix[i][j] + 1)
    return matrix[len2][len1]