Comment calculer la distance entre les chaînes en utilisant php

Cet article présente principalement comment utiliser PHP pour calculer la distance entre les chaînes. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

Résumé

Résumé en une phrase : Quelle est la meilleure façon de résoudre le problème DP : analyser l'état puis dessiner un exemple + dessiner un tableau.

1. Quelle est la meilleure façon de résoudre le problème dp ?

Après analyse du statut, exemple + table à dessin

2. Quels sont les avantages du dessin ?

Après avoir dessiné le tableau, il est facile de programmer et il n'est pas facile de faire des erreurs, car vous avez une référence, vous pouvez écrire le code selon la référence

2. distance de la chaîne

Description du titre

La distance de Levenshtein, également connue sous le nom de distance d'édition, fait référence au nombre minimum d'opérations d'édition requises pour convertir une chaîne en l'autre entre deux chaînes. Les opérations d'édition autorisées incluent le remplacement d'un caractère par un autre, l'insertion d'un caractère et la suppression d'un caractère. L'algorithme de distance d'édition a été proposé pour la première fois par le scientifique russe Levenshtein, c'est pourquoi il est également appelé Distance de Levenshtein.

Ex :

Chaîne A : abcdefg

Chaîne B : abcdef

Atteindre l'objectif en ajoutant ou en supprimant le caractère "g" . Les deux options nécessitent une seule opération. Définissez le nombre de fois requis pour cette opération comme la distance entre deux chaînes.

Exigence :

Étant donné deux chaînes, écrivez un algorithme pour calculer leur distance d'édition.

Veuillez implémenter l'interface suivante

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

Description de l'entrée :

Saisissez deux chaînes

Description de la sortie :

Obtenez le calcul Résultat

Exemple 1

Entrée

abcdefg
abcdef

Sortie

1

Code (le code est faux)

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

Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'apprentissage de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !

Recommandations associées :

Comment utiliser PHP pour obtenir l'analyse des images dans les documents

PHP implémente simplement l'envoi d'e-mails et les empêche d'être traité comme du spam Traitement

Comment modifier l'adresse de l'image WordPress en un chemin relatif

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!