PHP で 1 回の編集で文字列を比較する方法

文字列の編集操作には、文字の挿入、文字の削除、文字の置換の 3 つがあります。 2 つの文字列を指定して、編集が 1 つだけ (またはゼロ) 必要かどうかを判断する関数を作成します。今日はそれを見てみましょう。必要に応じて参照してください。

例 1:

入力:

first = "pale"
second = "ple"
输出: True

例 2:

输入: 
first = "pales"
second = "pal"
输出: False

問題解決のアイデア 1

# ブルート フォース クラッキング、文字を最初から最後まで検索し、一致しない文字列が見つかった場合は、2 つの文字列の残りの文字列を直接比較して、一貫性がない場合は、一貫性を維持するために複数の機会を更新する必要があります。以下が等しい場合、このビットのみが異なり、一度更新できます。

コード実装:

class Solution {
    /** 
    * @param String $first 
    * @param String $second 
    * @return Boolean 
    */
    function oneEditAway($first, $second) {
        $fl = strlen($first);
        $sl = strlen($second);
        // 长度差 > 1 直接返回 false
        if (abs($fl - $sl) > 1) return false;
        // 为了方便接下来的判断，保持 $first 更长
        if ($sl > $fl) return $this->oneEditAway($second, $first);
        for ($i = 0; $i < $sl; $i++) {
            // 如果其中一位不一致，则比较剩余字符串是否一致
            if ($first[$i] != $second[$i]) {
                return substr($first, $i + 1) == substr($second, $fl == $sl ? $i + 1 : $i);
            }
        }
        return true;
    }}

ダブル ポインター

同じ文字列を最初から最後まで検索し、見つかった場合は停止します。これは、同じ文字列の先頭から最大インデックス値を取得し、末尾から最小インデックス値を取得することと同じです。それらの長さの差が < 1 の場合、1 つの編集は等しくなります。

たとえば、観覧席の先生の 2 つの文字列、最初からトラバースします。同じ文字列の最大インデックス値は 0 です。最後からトラバースを開始します。同じ文字列の最小インデックス値は 1、0、do同じ位置で停止しない 一度位置を変更して同じにすることはできません。

コードの実装:

class Solution {
    /** 
    * @param String $first 
    * @param String $second 
    * @return Boolean 
    */
    function oneEditAway($first, $second) {
        $fl = strlen($first);
        $sl = strlen($second);
        if (abs($fl - $sl) > 1) return false;
        $i = 0; $j = $fl - 1; $k = $sl - 1;
        // 正序获取两个字符串相同字符的最大 索引值
        while ($i < $fl && $i < $sl && $first[$i] == $second[$i]) {
            $i++;
        }
        // 倒序获取两个字符串相同字符的最小索引值
        while ($j >= 0 && $k >= 0 && $first[$j] == $second[$k]) {
            $j--;
            $k--;
        }
        // 比较倒序最小的和正序最大的索引值差距，如果最多编辑一次，则要求两个差值都不能大于 1
        return $j - $i < 1 && $k - $i < 1;
    }}

推奨学習:

php ビデオ チュートリアル

以上がPHP で 1 回の編集で文字列を比較する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。