Edit Distance -- leetcode

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

假設我們要將字符串str1變成str2
sstr1(i)是str1的子串，范圍[0到i），sstr1(0)是空串
sstr2(j)是str2的子串，同上
d(i,j)表示將sstr1(i)變成sstr2(j)的編輯距離

首先d(0,t),0<=t<=str1.size()和d(k,0)是很明顯的。
當我們要計算d(i,j)時，即計算sstr1(i)到sstr2(j)之間的編輯距離,
此時，設sstr1(i)情勢是somestr1c；sstr2(i)形如somestr2d的話，
將somestr1變成somestr2的編輯距離已知是d(i⑴,j⑴)
將somestr1c變成somestr2的編輯距離已知是d(i,j⑴)
將somestr1變成somestr2d的編輯距離已知是d(i⑴,j)
那末利用這3個變量，就能夠遞推出d(i,j)了：
如果c==d，明顯編輯距離和d(i⑴,j⑴)是1樣的
如果c!=d，情況略微復雜1點，

1. 如果將c替換成d，編輯距離是somestr1變成somestr2的編輯距離 + 1，也就是d(i⑴,j⑴) + 1
2. 如果在c后面添加1個字d，編輯距離就應當是somestr1c變成somestr2的編輯距離 + 1，也就是d(i,j⑴) + 1
3. 如果將c刪除，那就是要將somestr1編輯成somestr2d，距離就是d(i⑴,j) + 1

   那最后只需要看著3種誰最小，就采取對應的編輯方案了。

在下面的實現代碼中，我使用轉動數組，代替了2維數組。 而且只分配了1個數組。

另外，變量dist_i1_j1 表示 d(i⑴, j⑴)

                    dist_i_j      表示 d(i,j)

                    dist_i1_j    表示d(i⑴, j)

                    dist_i_j1    表示d(i, j⑴)

另外，下面代碼中， 其實變量

都是可以省掉的。

不過留著，可以更直觀1點。

在leetcode上的實際履行時間為28ms。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈