分析出狀態(tài)后 實例+畫表

畫出來表之后編程也好編，不容易出錯，因為有了參照，可以照著參照來編寫代碼

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

Ex：

字符串A:abcdefg

字符串B: abcdef

通過增加或是刪掉字符”g”的方式達到目的。這兩種方案都需要一次操作。把這個操作所需要的次數(shù)定義為兩個字符串的距離。

要求：

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

請實現(xiàn)如下接口

/* 功能：計算兩個字符串的距離 * 輸入： 字符串A和字符串B * 輸出：無 * 返回：如果成功計算出字符串的距離，否則返回-1 html' target='_blank'>public static int calStringDistance (String charA, String charB) return 0; }

輸入兩個字符串

得到計算結(jié)果

示例1

abcdefgabcdef

1

 ?php1、這是一個dp的題目2、而且是一個線性dp3、f(i)(j)怎么得到f(i)(j)4、dp就是刷表，這里明顯是刷2維表5、f(i)(j)表示什么呢：表示字符串1的前i和字符串2的前就j個的距離，那么最終所有就是f(len(str1))(len(str2))6、狀態(tài)轉(zhuǎn)移方程呢：如果字符串1的最后一個和字符串2的最后一個字符相等，那么f(i)(j)=f(i-1)(j-1)，不相等，那么f(i)(j)=min(f(i-1)(j),f(i)(j-1))7、想的差不都的時候就直接到excel中根據(jù)實例畫表即可，不容易出錯且清晰快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);? 

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，更多相關(guān)內(nèi)容請關(guān)注PHP ！

相關(guān)推薦：

如何使用php獲得文檔中圖片的解析

PHP簡單實現(xiàn)發(fā)送郵件和防被當成垃圾郵件處理

如何修改WordPress圖片地址為相對路徑

以上就是如何使用php計算字符串之間的距離的詳細內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。