先給一個(gè)例子，兩個(gè)字符串eeba和abca相似度是多少呢，edit distance是一個(gè)很好的度量，定義從字符串a(chǎn)變到字符串b，所需要的最少的操作步驟（插入，刪除，更改）為兩個(gè)字符串之間的編輯距離。

對(duì)于eeba,abca它們之間的編輯距離為3，可以按照上面的操作步驟（不是唯一的）將eeba變到abca，1.將e變?yōu)閍 2.刪除e 3.添加c 共3個(gè)步驟。

典型的動(dòng)態(tài)規(guī)劃問題。

EDIT[i,j]表示對(duì)于字符串a(chǎn)從1到i的子串和字符串b從1到j(luò)的字串的編輯距離。（字符串下標(biāo)從1開始)

EDIT[i - 1,j] + 1表示對(duì)a 在i 位置刪除delete操作

EDIT[i,j - 1] + 1 表示insert添加操作

EDIT[i-1, j - 1] + f(x[i],y[j])這里如果x[i] == y[j] 則 f(x[i],y[j]) == 0 否則 ==1

表示不變或者是modify操作。

如果需要記錄編輯過程如第一幅圖所示，需要用二維數(shù)組記錄下動(dòng)態(tài)規(guī)劃過程的路徑信息，即記錄下前一步驟的位置索引信息。

如下圖

?

class Solution { public:int minDistance(string word1, string word2) {// Start typing your C/C++ solution below// DO NOT write int main() functionint row = word1.length() + 1;int col = word2.length() + 1;vector<vector<int> > f(row, vector<int>(col));for (int i = 0; i < row; i++)f[i][0] = i;for (int i = 0; i < col; i++)f[0][i] = i;for (int i = 1; i < row; i++)for (int j = 1; j < col; j++){if (word1[i-1] == word2[j-1])f[i][j] = f[i-1][j-1];elsef[i][j] = f[i-1][j-1] + 1;f[i][j] = min(f[i][j], min(f[i-1][j]+1, f[i][j-1]+1));}return f[row-1][col-1];} };

?

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/lihaozy/archive/2012/12/31/2840152.html

總結(jié)

以上是生活随笔為你收集整理的[leetcode]Edit Distance的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。