Routes not working after deploying Laravel 5 project into hosting

In the end I could solve it adding

RewriteBase /

to my .htaccess file in the public folder.

This is my complete .htaccess file:

<IfModule mod_rewrite.c>
<IfModule mod_negotiation.c>
    Options -MultiViews
</IfModule>

RewriteEngine On
RewriteBase /

# Redirect Trailing Slashes...
RewriteRule ^(.*)/$ /$1 [L,R=301]

# Handle Front Controller...
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^ index.php [L]

The most strange thing is I already had tried that, because that's how I solved the same issue with Laravel 4. What made it work was changing

RewriteBase /

to the incorrect

RewriteBase ../

and then changing it back to

RewriteBase /

And misteriously it solved.

I hope this helps anyone. It's 5:22 and I need some sleep