def edit_distance(s1, s2):
    """
    Levenshtein distance
    Complexity: O(len(s1)*len(s2))
    """
    n = len(s1)
    m = len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for j in range(1, m):
        dp[0][j] = j

    for i in range(1, n):
        dp[i][0] = i

    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])

    return dp[-1][-1]