首頁 >後端開發 >php教程 >如何使用php計算字串之間的距離

如何使用php計算字串之間的距離

不言原創: 2018-07-10 11:28:281594瀏覽

這篇文章主要介紹了關於如何使用php計算字串之間的距離，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

一、總結

一句話總結：解決dp問題最好的方法是什麼：分析出狀態後實例畫表。

1、解決dp問題最好的方法是什麼？

分析出狀態後實例畫表

2、畫圖的好處？

畫出來表格之後程式設計也好編，不容易出錯，因為有了參照，可以照參照來寫程式碼

二、計算字串的距離

題目描述

Levenshtein 距離，又稱為編輯距離，指的是兩個字串之間，由一個轉換成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。編輯距離的演算法是先由俄國科學家Levenshtein提出的，故又叫Levenshtein Distance。

Ex：

字串A:abcdefg

字串B: abcdef

透過增加或刪除字元」g」的方式達到目的。這兩種方案都需要一次操作。把這個運算所需的次數定義為兩個字串的距離。

要求：

給定任兩個字串，寫出一個演算法計算它們的編輯距離。

請實作下列介面

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