PHPを使用して文字列間の距離を計算する方法-PHPチュートリアル-php.cn

PHPを使用して文字列間の距離を計算する方法

不言

リリース： 2023-04-02 21:58:01

オリジナル

1575 人が閲覧しました

この記事では、主に PHP を使用して文字列間の距離を計算する方法を紹介します。これには特定の基準値があります。ここで共有します。必要な友人はそれを参照してください。

1. まとめ

一文で要約: dp 問題を解決する最良の方法は何ですか: ステータスを分析した後、サンプルテーブルを作成します。

1. dp 問題を解決する最善の方法は何ですか?

状況を分析した後、表を描く例

2. 絵を描くメリットは何ですか?

表を書いた後はプログラミングが簡単で、リファレンスがあるので、それに従ってコードを書くことができ、間違いが起こりにくいです

2. 距離を計算する文字列の数

タイトルの説明

編集距離とも呼ばれるレーベンシュタイン距離は、2 つの文字列間で一方の文字列をもう一方の文字列に変換するために必要な編集操作の最小数を指します。許可される編集操作には、ある文字を別の文字に置き換える、文字を挿入する、文字を削除するなどがあります。編集距離のアルゴリズムはロシアの科学者レーベンシュタインによって最初に提案されたため、レーベンシュタイン距離とも呼ばれます。

例：

文字列 A: abcdefg

文字列 B: abcdef

文字 "g" を追加または削除することで目的を達成します。どちらのオプションでも 1 回の操作が必要です。この操作に必要な回数を 2 つの文字列間の距離として定義します。

要件:

任意の 2 つの文字列が与えられた場合、その編集距離を計算するアルゴリズムを作成します。

次のインターフェースを実装してください

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

ログイン後にコピー

入力説明:

2 つの文字列を入力

出力説明:

計算結果を取得します

例 1

入力

abcdefg
abcdef

ログイン後にコピー

出力

ログイン後にコピー

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 中国語 Web サイトをご覧ください。