LeetCode -- Edit Distance

LeetCode -- Edit Distance

題目描述：


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


就是求從單詞1(word1)變化到單詞2(word2)的最小變化次數，每次變化只能：添加、刪除或更新1個字符。
本題是一道典型的DP題，遞推公式：
假設dp[i,j]表示word1前i-1個字符到word2的前j-1個字符最小變化次數。
首先對dp做初始化，當word1為空串時，dp[i,0]為i（情況只可能是添加i個字符），其中i∈[0,n]。同理，dp[0,i]的初始化也可以看作是word2為空串時，從word1變到空串的情況數同樣為i（即只可能是移除i個字符）。


I.當word1[i]與word2[j]相等時，無需更新次數，即dp[i+1,j+1] = dp[i,j]


II.當word1[i]與word2[j]不等時，當前的比較的“上一次比較情況”可以分3種可能：
1. word1[i-1]與word2[j-1]比較
2. word1[i]與word2[j-1]
3. word[i-1]與word2[j]。
只需要從存放這3種情況中比較結果的dp數組中判斷哪種情況最小即可。
即，
dp[i+1,j+1]= 最小值（dp[i,j+1], dp[i+1,j], dp[i,j]）




實現代碼：

public class Solution {
    public int MinDistance(string word1, string word2) {
        var dp = new int [word1.Length+1, word2.Length+1];
	
    	for(var i = 0;i < word1.Length + 1; i++){
    		dp[i,0] = i;
    	}
    	for(var i = 0;i < word2.Length + 1; i++){
    		dp[0,i] = i;
    	}
    	
    	for(var i = 0; i < word1.Length; i++){
    		for(var j = 0;j < word2.Length; j++){
    			if(word1[i] == word2[j]){
    				dp[i+1,j+1] = dp[i,j];
    			}
    			else{
    				var min = Math.Min(Math.Min(dp[i,j], dp[i,j+1]), dp[i+1,j]);
    				dp[i+1,j+1] = min + 1;
    			}
    		}
    	}
    	
    	return dp[word1.Length, word2.Length];
    }
}