How to compare strings in one edit in PHP

There are three editing operations for strings: insert a character, delete a character, or replace a character. Given two strings, write a function to determine whether they need only one (or zero) edits. Let’s take a look at it today, and you can refer to it if you need it.

Example 1:

Input:

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

Example 2:

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

Problem-solving ideas 1

Brute force cracking, search characters from the beginning to the end. If an unequal one is encountered, directly compare the remaining strings of the two to see if they are consistent. If they are inconsistent , then more than one opportunity is needed to update to maintain consistency. If the following ones are equal, only this bit is different, and it can be updated once.

Code implementation:

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

Double pointers

Search for the same string from beginning to end, and stop when encountering different ones , which is equivalent to obtaining the maximum index value of the same string from the beginning and the minimum index value from the end. If their length difference is

For example, bleacher teacher two strings, traverse from the beginning, the maximum index value of the same string is 0, start traversing from the end, the minimum index value of the same string is 1, 0, do not stop at the same A position cannot be modified once to make it the same.

Code implementation:

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

Recommended learning: php video tutorial

The above is the detailed content of How to compare strings in one edit in PHP. For more information, please follow other related articles on the PHP Chinese website!