PHP를 사용하여 문자열 사이의 거리를 계산하는 방법-PHP 튜토리얼-php.cn

PHP를 사용하여 문자열 사이의 거리를 계산하는 방법

不言

풀어 주다： 2023-04-02 21:58:01

원래의

1574명이 탐색했습니다.

이 글은 주로 PHP를 사용하여 문자열 사이의 거리를 계산하는 방법을 소개합니다. 특정 참조 값이 있습니다. 이제 도움이 필요한 친구들이 참고할 수 있습니다.

1. 요약: dp What 문제를 해결하는 가장 좋은 방법은 상태를 분석한 다음 예제를 사용하고 표를 그리는 것입니다.

1. DP 문제를 해결하는 가장 좋은 방법은 무엇인가요?

상태 분석 후 예시+드로잉 테이블 활용

2. 드로잉의 장점은 무엇인가요?

표를 그린 후 프로그래밍하기 쉽고, 실수하기가 쉽지 않습니다. 참조가 있으므로 참조에 따라 코드를 작성할 수 있습니다.

2 문자열의 거리를 계산합니다.

문제 설명

Levenshtein 거리(편집 거리라고도 함)는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 작업 수를 나타냅니다. 허용되는 편집 작업에는 한 문자를 다른 문자로 바꾸기, 문자 삽입 및 삭제가 포함됩니다. 편집 거리 알고리즘은 러시아 과학자 Levenshtein이 처음 제안했기 때문에 Levenshtein Distance라고도 합니다.

예:

String A: abcdefg

String B: abcdef

문자 "g"를 추가하거나 삭제하면 목적이 달성됩니다. 두 옵션 모두 하나의 작업이 필요합니다. 이 작업에 필요한 횟수를 두 스트링 사이의 거리로 정의합니다.

요구 사항:

두 개의 문자열이 주어지면 편집 거리를 계산하는 알고리즘을 작성하세요.

다음 인터페이스를 구현하세요

/*  功能：计算两个字符串的距离
 *  输入： 字符串A和字符串B
 *  输出：无
 *  返回：如果成功计算出字符串的距离，否则返回-1
 */
     public   static   int calStringDistance (String charA, String  charB)
    {
        return  0;
    }

로그인 후 복사

입력 설명:

두 개의 문자열을 입력하세요

출력 설명:

계산 결과 가져오기

예제 1

Input

abcdefg
abcdef

로그인 후 복사

Output

로그인 후 복사

2. 틀림 )

<?php
/*
1、这是一个dp的题目
2、而且是一个线性dp
3、f(i)(j)怎么得到f(i)(j)
4、dp就是刷表，这里明显是刷2维表
5、f(i)(j)表示什么呢：表示字符串1的前i和字符串2的前就j个的距离，那么最终所有就是f(len(str1))(len(str2))
6、状态转移方程呢：如果字符串1的最后一个和字符串2的最后一个字符相等，那么f(i)(j)=f(i-1)(j-1)，
不相等，那么f(i)(j)=min(f(i-1)(j),f(i)(j-1))
7、想的差不都的时候就直接到excel中根据实例画表即可，不容易出错且清晰快
*/
while($str1=trim(fgets(STDIN))){
    $str2=trim(fgets(STDIN));
    $len1=strlen($str1);
    $len2=strlen($str2);
    $dp=null;
    for($i=0;$i<=$len2;$i++){
        $dp[]=array_fill(0,intval($len1)+1,0);
    }
    for($i=0;$i<=$len1;$i++){
        $dp[0][$i]=$i;
    }
    for($i=0;$i<=$len2;$i++){
        $dp[$i][0]=$i;
    }
    for($i=1;$i<=$len2;$i++){//行
        for($j=1;$j<=$len1;$j++){//列
            //如果str1[$i-1]在str2:0-$j-1中找到，
            $str1_2=substr($str1,0,$j);
            if(strpos($str1_2,$str2[$i-1])!==false){
                $dp[$i][$j]=$dp[$i-1][$j-1];
            }else{
                $dp[$i][$j]=max($dp[$i][$j-1],$dp[$i-1][$j]);
            }
        }
    }
    echo $dp[$len2][$len1].PHP_EOL;
    //print_r($dp);
}
?>

로그인 후 복사

위 내용은 이 글의 전체 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지를 참고해주세요!