I got an error about replace a space with hyphen for mod rewrite

Hello,

I tried to create a mod rewrite to list all cities in more friendly urls. Everything worked fine, except the space between two-word city show "%20". When I used Replace on php code to show a hyphen between two-words cities, then no results show up.

Here is my htaccess code:
RewriteRule ^(city|state)/([^/]*)-online-dating\/$ /search_results.php?$1=$2&mark=1 [QSA,L]
RewriteRule ^(city|state)/([^/]*)-online-dating\/pg\/([0-9]+)\/$ /search_results.php?$1=$2&pg=$3&mark=1 [QSA,L]

RewriteRule ^([^/]*)\/([^/]*)\/([^/]*)\/([0-9]+)\_([^/]*)\/$ /view_profile.php?id=$4 [QSA,L]
RewriteRule ^search_results\/([^/]*)\/([^/]*)\/$ /search_results.php?$1=$2 [QSA,L]
RewriteRule ^search_results\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/$ /search_results.php?$1=$2&$3=$4 [QSA,L]
RewriteRule ^search_results\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/$ /search_results.php?$1=$2&$3=$4&$5=$6 [QSA,L]
RewriteRule ^search_results\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/$ /search_results.php?$1=$2&$3=$4&$5=$6&$7=$8 [QSA,L]
RewriteRule ^search_results\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/([^/]*)\/$ /search_results.php?$1=$2&$3=$4&$5=$6&$7=$8&$9=$10 [QSA,L]

Here is my php code on search_results.php file:
echo "<a href='/city/".strtolower(str_replace(' ','-',$mem["sb_city"]))."-online-dating/' class='small_link'
title='All members from ".$mem["sb_city"]."'>".$mem["sb_city"]."</a>, ";

Can anyone please tell me what I need to change to get it works?

Thanks.