leetcode解题: Edit Distance (72)

发表于 | 分类于

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

解法：DP with O(N^2) Time and O(N^2) Space

双字符串统计min的问题，容易想到用DP解决。
假设dp[i][j] 表示前i个字符和前j个字符的子串，convert substr1 to substr2的minimum steps.
那么对于初始条件我们容易得到：

  • dp[0][j] = j
  • dp[i][0] = i
    这里表示的是，如果其中一个是空字符，那么你要么插入j个字符或者删除j个字符，任何一种情况都是j个操作
    当考虑状态方程的时候，要考虑i和j两位置上的字符是否相等，分两种情况:
    1 charAt(i) == charAt(j)
    当最后比较的字符相同时，有三种情况/操作可能出现
    1 可能最小值来自于i - 1和j - 1的匹配，
    2 或者是i - 1转为j的匹配，那么就要加上1表示从i字符串删除一位变为i - 1字符串的操作。
    3 也可能是把i匹配为j - 1的字符串，然后最后加上第j个字符(insert操作）
    dp[i][j] = Min(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1)

2 charAt(i) != charAt(j)
相类似于上面一种情况，唯一不同的是，dp[i - 1][j - 1]要加上1表示把第i位转化为第j位的操作
dp[i][j] = Min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int minDistance(String word1, String word2) {
		
	// input validation
	if (word1 == null && word2 == null) {
		return 0;
	}
	
	if (word1 == null) {
		return word2.length();
	}
	
	if (word2 == null) {
		return word1.length();
	}
	
	// DP
	
	int[][] dp = new int[word1.length() + 1][word2.length() + 1];
	
	// initialize
	for (int i = 0; i <= word1.length(); i++) {
		dp[i][0] = i;
	}
	
	for (int j = 0; j <= word2.length(); j++) {
		dp[0][j] = j;
	}
	
	for (int i = 1; i <= word1.length(); i++) {
		for (int j = 1; j <= word2.length(); j++) {
			if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
				// make sure you get the index right, since we added 1 to the array, we need to subtract 1 
				// to get the index positions
				dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) + 1);
			} else {
				dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j], dp[i][j - 1]) + 1);
			}
		}
	}
	
	return dp[word1.length()][word2.length()];
}