Geeks面试题： Edit Distance

Problem: Given two strings of size m, n and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another.

http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/

两个一维表的C++实现：

int editDisDP(string s1, string s2)
{
	vector<vector<int> > ta(2, vector<int>(s2.size()+1));
	bool flag = false;
	for (int i = 0; i <= s2.size(); i++)
	{
		ta[!flag][i] = i;
	}

	for (int i = 0; i < s1.size(); i++)
	{
		ta[flag][0] = ta[!flag][0]+1;
		for (int j = 0; j < s2.size(); j++)
		{
			if (s1[i] == s2[j])
			{
				ta[flag][j+1] = ta[!flag][j];
			}
			else
			{
				ta[flag][j+1] = min(min(ta[!flag][j+1], ta[flag][j]),
					ta[!flag][j]) + 1;
			}
		}
		flag = !flag;
	}
	return ta[!flag][s2.size()];
}