>백엔드 개발 >PHP 문제 >PHP에서 한 번의 편집으로 문자열을 비교하는 방법

PHP에서 한 번의 편집으로 문자열을 비교하는 방법

醉折花枝作酒筹
醉折花枝作酒筹앞으로
2021-07-07 15:17:202318검색

문자열 편집 작업에는 문자 삽입, 문자 삭제, 문자 바꾸기라는 세 가지 작업이 있습니다. 두 개의 문자열이 주어지면 편집이 한 번만 필요한지(또는 전혀 없는지) 결정하는 함수를 작성하세요. 오늘은 한번 살펴보시고, 필요하시면 참고하시면 됩니다.

PHP에서 한 번의 편집으로 문자열을 비교하는 방법

예 1:

입력:

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

예 2:

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

문제 해결 아이디어 1

무차별 대입 크래킹, 처음부터 끝까지 문자 검색 퀄 원 이 발생하면 두 문자열의 나머지 문자열이 일치하는지 직접 비교하십시오. 일치하지 않는 경우 일관성을 유지하기 위해 업데이트하는 데 두 번 이상의 기회가 필요합니다. 다음의 내용이 동일할 경우 이 비트만 다른 것이며, 1회 업데이트가 가능합니다.

코드 구현:

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

이중 포인터

처음부터 끝까지 동일한 문자열을 검색하고, 다른 문자열을 만나면 중지합니다. 이는 동일한 문자열의 최대 인덱스 값을 얻는 것과 같습니다. 시작 및 끝 인덱스 값의 최소값, 길이 차이가

예를 들어 두 문자열 관람석 선생님을 처음부터 순회하면 같은 문자열의 최대 인덱스 값은 0이고, 끝에서 순회하면 같은 문자열의 최소 인덱스 값은 1, 0이며 그렇지 않습니다. 같은 위치에 멈추면 한번 수정해서 똑같아질 수 없습니다.

코드 구현:

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에서 한 번의 편집으로 문자열을 비교하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 hxd.life에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제