[LeetCode]Edit Distance

    仍然是String的题目，自然又想到DP的方法，两个String，二维DP。对于String s和p，[i，j]表示s的前i个char和p的前j个char的最短距离，对于[i，j]，有以下三种情况：

• [i, j] = [i - 1, j - 1] (+ 1)，加一取决于s的第i个和p的第j个match与否，这种情况对应于replace一个字符，或者不需要repalce
• [i , j] = [i - 1,  j] + 1，这种情况对应于插入或者删除s的第i个字符
• [i , j] = [i,  j - 1] + 1，这种情况对应于插入或者删除p的第j个字符

假设输入string分别长m和n，时间复杂度和空间复杂度都是O(m * n)，代码如下：

	public class Solution {
	private int min (int a, int b, int c) {
	if (a <= b && a <= c)
	return a;
	else if (b <=a && b <= c)
	return b;
	else
	return c;
	}
	public int minDistance(String word1, String word2) {
	int len1 = word1.length();
	int len2 = word2.length();
	int[][] arr = new int[len1 + 1][len2 + 1];
	arr[0][0] = 0;
	for (int i = 1; i <= len1; i++) {
	arr[i][0] = i;
	}
	for (int j = 1; j <= len2; j++) {
	arr[0][j] = j;
	}
	for (int i = 0; i < len1; i++) {
	for (int j = 0; j < len2; j++) {
	int cost = arr[i][j];
	if (word1.charAt(i) != word2.charAt(j)) {
	cost++;
	}
	arr[i + 1][j + 1] = min(arr[i][j + 1] + 1, arr[i + 1][j] + 1, cost);
	}
	}
	return arr[len1][len2];
	}
	}

view raw edit distance.java hosted with ❤ by GitHub

我们可以用滚动数组把空间优化到O(n)，代码如下：

	class Solution {
	public:
	int minDistance(string word1, string word2) {
	int len1 = word1.size(), len2 = word2.size();
	//dp[i][j] represent distance between first i chars in word1 and first j chars in word2
	//dp[i][j] = dp[i - 1][j - 1], if word1[i] == word2[j]
	//otherwise, dp[i][j] = max(dp[i]][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
	vector<int> dp(len2 + 1, 0);
	for(int j = 0; j < len2; ++j)dp[j + 1] = j + 1;
	for(int i = 0; i < len1; ++i)
	{
	int helper = dp[0];
	dp[0] = i + 1;
	for(int j = 0; j < len2; ++j)
	{
	int cache = dp[j + 1];
	if(word1[i] == word2[j])
	dp[j + 1] = helper;
	else
	dp[j + 1] = min(min(dp[j], dp[j + 1]), helper) + 1;
	helper = cache;
	}
	}
	return dp[len2];
	}
	};

view raw Edit Distance_2.cpp hosted with ❤ by GitHub