Comment comparer des chaînes en une seule modification en PHP

Il existe trois opérations d'édition pour les chaînes : insérer un caractère, supprimer un caractère ou remplacer un caractère. Étant donné deux chaînes, écrivez une fonction pour déterminer si elles n’ont besoin que d’une (ou de zéro) modification. Jetons-y un coup d'œil aujourd'hui et vous pourrez vous y référer si vous en avez besoin.

Exemple 1 :

Entrée :

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

Exemple 2 :

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

Idée de résolution de problèmes 1

Craquage par force brute, rechercher des caractères du début à la fin, si une première qualité est rencontré, comparez directement si les chaînes restantes des deux sont cohérentes. Si elles sont incohérentes, il faudra plus d'une opportunité de mise à jour pour maintenir la cohérence. Si les suivants sont égaux, seul ce bit est différent, et il peut être mis à jour une fois.

Implémentation du code :

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;
    }}

Pointeurs doubles

Recherchez la même chaîne du début à la fin et arrêtez-vous lorsque vous en rencontrez une différente, ce qui équivaut à obtenir la valeur d'index maximale de la même chaîne à partir de le début et le minimum à partir de la fin des valeurs d'index, si leurs différences de longueur sont < 1, alors une modification peut être égale.

Par exemple, si deux chaînes du professeur de blanchisseur sont parcourues depuis le début, la valeur d'index maximale de la même chaîne est 0, et parcourues depuis la fin, la valeur d'index minimale de la même chaîne est 1, 0, et elles le font ne s'arrête pas à la même position, alors il ne peut pas être modifié une seule fois et ce sera le même.

Implémentation du code :

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;
    }}

Apprentissage recommandé : Tutoriel vidéo php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!