Permalinks Messed up

I am trying to fix a problem, the links are all messed up and look like

I have tried this code in the public_html folder in a .htaccess file, the links are now working with index.php/%postname%/ but I need to get rid of the index.php

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

# END WordPress

Any Help would be amazing. Thanks

After hours of searching and reading,
This is how I solved the Problem.

Step 1: Create a .htaccess file in the root folder and put this code there.

# BEGIN
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

# END 

Step 2: is Mentioned here