golang刷leetcode動態(tài)規(guī)劃之如何編輯距離

這篇文章主要介紹golang刷leetcode動態(tài)規(guī)劃之如何編輯距離，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

十余年品牌的成都網站建設公司,成百上千企業(yè)網站設計經驗.價格合理,可準確把握網頁設計訴求.提供定制網站建設、商城建設、微信平臺小程序開發(fā)、成都響應式網站建設公司等服務,我們設計的作品屢獲殊榮,是您值得信賴的專業(yè)網站設計公司。

給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數(shù) 。

你可以對一個單詞進行如下三種操作：

插入一個字符

刪除一個字符

替換一個字符

示例 1:

輸入: word1 = "horse", word2 = "ros"輸出: 3解釋: horse -> rorse (將 'h' 替換為 'r')rorse -> rose (刪除 'r')rose -> ros (刪除 'e')

示例 2:

輸入: word1 = "intention", word2 = "execution"輸出: 5解釋: intention -> inention (刪除 't')inention -> enention (將 'i' 替換為 'e')enention -> exention (將 'n' 替換為 'x')exention -> exection (將 'n' 替換為 'c')exection -> execution (插入 'u')

解題思路：

編輯距離又稱levenshtein距離，用來衡量兩個字符串的相似度，假設倆字符串分別為word1和word2，用m[i][j]存word1[0:i],word2[0:j]（左閉右開）的編輯距離，對于i,和j位置編輯距離m[i+1][j+1]；

1，如果word1[i]==word2[j],則編輯距離是

A，m[i][j]，word1[0:i],word2[0:j]（左閉右開）的編輯距離

B，m[i][j+1]+1，word1[0:i],word2[0:j＋1]（左閉右開）的編輯距離

C，m[i+1][j]+1，word1[0:i＋1],word2[0:j]（左閉右開）的編輯距離

這3種情況下最小者

2，如果word1[i]!=word2[j],則編輯距離是

上述3個分支中，A替換為m[i][j]＋1

3，由于m[i+1][j+1]用到了m[i][j+1]，m[i+1][j]，m[i][j]，所以采用遞增循環(huán)。

4，初始條件，為了便于初始化，我們這里有個優(yōu)化技巧：在word1和word2之前加一個空格，則：

A，m[0][0]=0

B，m[i][0]=i

C，m[0][j]=j

func minDistance(word1 string, word2 string) int {    if word1==""{        return len(word2)    }    if word2==""{        return len(word1)    }    m:=make([][]int,len(word1)+1)    for i:=0;i        m[i]=make([]int,len(word2)+1)    }     for i:=1;i     m[i][0]=i     }      for j:=1;j      m[0][j]=j      }    for i:=1;i        for j:=1;j            diff:=0            if word1[i-1]!=word2[j-1]{                diff=1            }            m[i][j]=min3(m[i-1][j]+1,m[i][j-1]+1,m[i-1][j-1]+diff)        }    }    return m[len(word1)][len(word2)]}
func min3(a,b,c int)int{    if a<=b && a<=c{        return a    }
    if b<=a&&b<=c{        return b    }    return c}

以上是“golang刷leetcode動態(tài)規(guī)劃之如何編輯距離”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

            
            
                        

            本文題目：golang刷leetcode動態(tài)規(guī)劃之如何編輯距離            

            網頁鏈接：http://weahome.cn/article/ieipso.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

golang刷leetcode動態(tài)規(guī)劃之如何編輯距離

其他資訊

網站制作

企業(yè)服務

網站建設

服務器托管