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
①字符串(string1+char1,string2+char2)的最小子序列茎截，可以分解為子問題(string1+char1,string2)，(string1,string2+char2)；(string1,string2)的最小編輯距離的解汪榔，且此解具有無后效性——最優(yōu)子結構
②反過來(string1,string2)的解在(string1+char1,string2)回溺，
(string1,string2+char2)，(string1+char1,string2+char2)都要被使用——重疊子問題
符合動態(tài)規(guī)劃條件，假設 F(i,j)是 string1 從 0 到 i 子串和 string2 從 0 到 j 子串的最小編輯距離累贤。轉移方程：
F(i+1,j+1) = min { f(i+1,j)+1, f(i,j+1)+1,
f(i1,j1)+(string1[i+1]==string2[j+1]?0:1) }，
需要用一個 m*n 矩陣存放中間結果少漆，時間復雜度是 O(m,n)臼膏，空間復雜度是
O(m,n)，但是可以優(yōu)化.
public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if(len1 > len2){
return minDistance(word2, word1);
}
int dp[] = new int[len2+1];
for(int i = 0; i<=len2; i++)
dp[i] = i;
int last, temp;
for(int i = 1; i<=len1; i++){
dp[0] = i;
last = i-1;
for(int j = 1; j<=len2; j++){
temp = dp[j];
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[j] = last;
}else{
dp[j] = 1 + Math.min(last, Math.min(dp[j-1], dp[j]));
}
last = temp;
}
}
return dp[len2];
}
}
這里有兩個技巧優(yōu)化 m*n 的空間復雜度示损。
①從左往右填 F(i,j)時渗磅，依賴上一行的 F(i-1,j),F(i-1,j-1)，以及本行的前一個數F(i,j-1)，F(i,j-1)剛生成始鱼，可以直接用论巍，F(i-1,j)在本行尚未被覆蓋掉，也可以直接用风响，只要用一個臨時變量保存 F(i-1,j-1)嘉汰，就可以是空間復雜度降到 O(n)。
②line 5 的轉換使得數組長度進一步降到 min(m,n)状勤。
本問題還有其他方法解鞋怀，
