How to calculate distance between strings using php

This article mainly introduces how to use PHP to calculate the distance between strings. It has a certain reference value. Now I share it with you. Friends in need can refer to it

1. Summary

Summary in one sentence: What is the best way to solve the dp problem: draw an example table after analyzing the status.

1. What is the best way to solve the dp problem?

After analyzing the status, example drawing a table

2. What are the benefits of drawing a picture?

It is easy to program after drawing the table, and it is not easy to make mistakes, because you have a reference, you can write the code according to the reference

2. Calculate the distance of strings

Title description

Levenshtein distance, also known as edit distance, refers to the minimum number of edit operations required to convert one string into the other between two strings. Permitted editing operations include replacing one character with another, inserting a character, and deleting a character. The algorithm of edit distance was first proposed by the Russian scientist Levenshtein, so it is also called Levenshtein Distance.

Ex：

String A: abcdefg

String B: abcdef

Achieve the purpose by adding or deleting the character "g" . Both options require one operation. Define the number of times required for this operation as the distance between two strings.

Requirements:

Given any two strings, write an algorithm to calculate their edit distance.

Please implement the following interface

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

Input description:

Input two strings

Output description:

Get the calculation result

Example 1

Input

abcdefg
abcdef

Output

1

2. Code (the code is incorrect)

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

The above is the entire content of this article. I hope it will be helpful to everyone’s study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

How to use PHP to obtain the analysis of images in documents

PHP simply implements sending emails and preventing them from being treated as spam Processing

How to modify the WordPress image address to a relative path

The above is the detailed content of How to calculate distance between strings using php. For more information, please follow other related articles on the PHP Chinese website!