def levenshtein_distance(s, t):
    """
    Computes the Levenshtein (insertions, deletions or substitutions are allowed)
    edit distance between two strings.
    """
    # Implementation of the Wagner–Fischer algorithm
    # https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
    m, n = len(s), len(t)
    dist = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        dist[i][0] = i
    for j in range(1, n + 1):
        dist[0][j] = j
    for j in range(1, n + 1):
        for i in range(1, m + 1):
            substitution_cost = 0 if s[i - 1] == t[j - 1] else 1
            dist[i][j] = min(
                dist[i - 1][j] + 1,
                dist[i][j - 1] + 1,
                dist[i - 1][j - 1] + substitution_cost,
            )
    return dist[m][n]