LeetCode Edit Distance 终极省内存方法

Edit Distance

Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (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个距离，那么直接复制前面的修改单词方案就可以了。

当两个字母不相同的时候，就需要增加一个修改距离，那么就需要在前面三种方案中选择最小的一种方案加1.

动态规划法，原始填二维表法：

int minDistance(string word1, string word2) {
		int n = word1.length();
		int m = word2.length();
		//把某些特殊情况的O(n)或O(m)变成O(1)，所以还是值得加两句的。
		if (n < 1) return m;
		if (m < 1) return n;

		vector<vector<int> > table(m+1, vector<int>(n+1));
		for (int i = 0; i <= n; i++)
		{
			table[0][i] = i;
		}
		for (int i = 0; i <= m; i++)
		{
			table[i][0] = i;
		}

		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (word2[i-1] == word1[j-1])
				{
					//注意：相同的情况下是直接按前面的方案计算就可以了
					//很难想出来的条件
					table[i][j] = table[i-1][j-1];
				}
				else 
				{
					int t = min(table[i-1][j], table[i][j-1]);
					table[i][j] = min(t, table[i-1][j-1]);
					table[i][j]++;
				}
			}
		}
		
		return table[m][n];
	}

节省内存，2行的二维表

int minDistance2(string word1, string word2) {
		int n = word1.length();
		int m = word2.length();
		//把某些特殊情况的O(n)或O(m)变成O(1)，所以还是值得加两句的。
		if (n < 1) return m;
		if (m < 1) return n;

		vector<vector<int> > table(2, vector<int>(n+1));
		for (int i = 0; i <= n; i++)
		{
			table[0][i] = i;
		}

		bool r = true;
		for (int i = 1; i <= m; i++)
		{
			table[r][0] = i;
			for (int j = 1; j <= n; j++)
			{
				if (word2[i-1] == word1[j-1])
				{
					table[r][j] = table[!r][j-1];
				}
				else 
				{
					int t = min(table[!r][j], table[r][j-1]);
					table[r][j] = min(t, table[!r][j-1]);
					table[r][j]++;
				}
			}
			r = !r;
		}
		
		return table[!r][n];
	}

终极省内存方法，直接使用一维表：

//要考虑到"aa" 与"aaaaaaaaaaa"的比较
class Solution {
public:
	int minDistance(string word1, string word2) {
		int n = word1.length();
		int m = word2.length();
		//把某些特殊情况的O(n)或O(m)变成O(1)，所以还是值得加两句的。
		if (n < 1) return m;
		if (m < 1) return n;

		vector<int> table(n+1);
		for (int i = 0; i <= n; i++)
			table[i] = i;

		for (int i = 1; i <= m; i++)
		{
			int upleft = table[0];
			table[0] = i;
			for (int j = 1; j <= n; j++)
			{
				int up = table[j];
				if (word2[i-1] != word1[j-1])
				{
					int t = table[j];
					table[j] = min(min(up, table[j-1]), upleft) + 1;
					upleft = t;
				}
				else swap(table[j], upleft);
			}
		}
		return table[n];
	}
};

//2014-2-10 update
	int minDistance(string word1, string word2) 
	{
		int *A[2];
		A[0] = new int[word2.length()+1];
		A[1] = new int[word2.length()+1];
		for (int i = 0; i <= word2.length(); i++) A[0][i] = i;

		bool idx = true;
		for (int i = 0; i < word1.length(); i++, idx = !idx)
		{
			A[idx][0] = i+1;
			for (int j = 0; j < word2.length(); j++)
			{
			    if (word1[i] == word2[j]) A[idx][j+1] = A[!idx][j];
				else A[idx][j+1] = min(A[idx][j], min(A[!idx][j+1], A[!idx][j]))+1;
			}
		}
		return A[!idx][word2.length()];
	}