[LeetCode] 72. 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

<Solution>

這題剛開始真的不太懂怎麼下手

後來看了一下資料，要運用到 dynamic programming 的方式 (參考資料)

想法如下

• dp[i][j]，代表的是從 word1[0..i-1] 變換到 word2[0..j-1]的最小步驟，1 <= i < word1.length(), 1<= j < word2.length()

• i = 0，也就是 dp 的 row 0，代表的是從空字串變成 word2，那其實就是將 word2 的每個字元，一個一個 insert 到 word1，所以 dp[0][j] = j

• j = 0，dp 的 col 0，代表從word1 變成空字串，就是把 word1 每個字元一個一個刪掉，所以 dp[i][0] = i

• 接著是一般情況，假設現在要求 dp[i][j]，代表是在看 word1[i-1]和 word2[j-1]，所以已經知道 dp[i-1][j-1]的值了，也就是知道如何將 word1[0..i-2] 轉換成 word2[0..j-2] ，那麼會有以下幾種情況

• word1[i-1] = word2[j-1]，這樣什麼都不用做，所以 dp[i][j] = dp[i-1][j-1]

• 需要 replace : replace(word1[i-1], word2[j-1])，所以 dp[i][j] = dp[i-1][j-1] + 1 (for replace)

• 需要 delete : word1[0..i-2] = word2[0..j-1]，所以 dp[i][j] = dp[i-1][j] + 1 (for delete)

• 需要 insert : word1[0..i-1] + word2[j-1] = word2[0..j-1]，所以 dp[i][j] = dp[i][j-1] + 1 (for insert)

這樣就可以找出推導的公式

if word1[i-1] = word[j-1], dp[i][j] = dp[i-1][j-1]

otherwise dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

code 如下
c++

	class Solution {
	public:
	int minDistance(string word1, string word2) {
	const int m = word1.length(), n = word2.length();
	vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
	//> row 0 : change "" to word2
	//> only need insert operation for each word
	for(int c = 0; c <= n; c++) {
	dp[0][c] = c;
	}
	//> col 0 : change word1 to ""
	//> only need delete operation for each word
	for(int r = 0; r <= m; r++) {
	dp[r][0] = r;
	}
	for(int r = 1; r <= m; r++) {
	for(int c = 1; c <= n; c++) {
	if(word1[r-1] == word2[c-1]) {
	//> if word1[r-1] = word2[c-1], no operation needed
	dp[r][c] = dp[r-1][c-1];
	}
	else {
	//> ifword1[r-1] != word2[c-1], there are there operations can use
	//> replace, delete, insert
	//> chose the min from those three operations
	dp[r][c] = min(dp[r-1][c-1], min(dp[r-1][c], dp[r][c-1])) + 1;
	}
	}
	}
	return dp[m][n];
	}
	};

view raw changeWord1ToWord2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun minDistance(word1: String, word2: String): Int {
	// dp[i][j]: min steps of changing word1[i] to word2[j]
	val dp = Array(word1.length+1) { IntArray(word2.length+1) {0} }
	// r = 0: word1 = "" and change "" to word2
	for(c in 0..word2.length) {
	dp[0][c] = c
	}
	// c = 0: change word2 to ""
	for(r in 0..word1.length) {
	dp[r][0] = r
	}
	for(r in 1..word1.length) {
	for(c in 1..word2.length) {
	if(word1[r-1] == word2[c-1]) {
	dp[r][c] = dp[r-1][c-1] // do nothing
	} else {
	dp[r][c] = Math.min(dp[r][c-1], Math.min(dp[r-1][c], dp[r-1][c-1])) + 1
	}
	}
	}
	return dp[word1.length][word2.length]
	}
	}

view raw edit_distance.kt hosted with ❤ by GitHub