How to match and replace one array values to another array keys if they both start with the same letters?

I have two arrays:

$array_one = array('AA','BB','CC');

And:

$replacement_keys = array
 (
 ""=>null,
 "BFC"=>'john',
 "ASD"=>'sara',
 "CSD"=>'garry'
);

So far I've tried

array_combine and to make a loop and try to search for values but can't really find a solution to match the keys of the second array with the values of the first one and replace it.

My goal is to make a final output:

$new_array = array
(
''=>null,
'BB' => 'john',
'AA' => 'sara',
'CC' => 'garry'
);

In other words to find a matching first letter and than replace the key with the value of the first array.

Any and all help will be highly appreciated.

via Chebli Mohamed