PHP面接問題ベスト5——スペースを置き換える

1つの文字列の各スペースを「%20」に置き換える関数を実装してください.例えば、文字列がWe Are Happyである.置換後の文字列は、We%20 Are%20 Happyである.
この問題について、私たちの最初の考えは文字列を順番に遍歴することであり、スペース文字に遭遇した場合、スペースを「20%」に置き換え、文字列の長さが長くなったため、置き換える前に、スペースの後ろの文字列をすべて2桁後ろに移動してから置き換えます.この構想のアルゴリズム複雑度はO(n^2)である.
面接官はこの考えに満足していないのは明らかです.彼はあなたにもっと効率的な考えがあるかどうかを聞きます.実は私たちのこの考え方の最大の問題は、1つのスペースに出会うたびに、後ろのすべての文字列が1回移動し、多くの文字列が何度も移動し、1文字ごとに1回移動できれば、効率が高くなります.
考えを変えて、後ろから前に移動して、各文字を最終的に移動する位置に一度に移動させて、繰り返し移動しません.まず文字列を繰り返して、文字列の長さとスペースの個数を得ます.これにより、置換後の文字列の全長を算出することができる.2つのポインタP 1,P 2,P 1が元の文字列の末尾を指し,P 2が置換後の文字列の末尾を指すとする.P 1を1つずつ前に移動し、P 1が指す文字をP 2に移動し、P 2も前に移動する.スペースに遭遇した場合、P 1は1マス移動し、%20はP 2の前に充填し、P 2は3マス前に移動する.これによりO(n)複雑度の置換が実現される.
実装コードは次のとおりです.

function replaceSpace($str)
{
    $len = strlen($str);
    $objStr = '';
    
    for($i=$len-1; $i>=0; $i--)
    {
        if($str[$i] == ' ')
            $objStr = '%20'.$objStr;
        else
            $objStr = $str[$i].$objStr;
    }
    
    return $objStr;
}