Longest Common Subsequence space optimized

This algorithm to find Longest Common Subsequence between two stings in space O(min(n,m)) rather than creating one array of two dimensions n*m, so the space is O(mn). where:

• n = length of first string
• m = length of second string

while actually we need only last two rows to compare lengths. so we will replace one array [n][m], to be two arrays each one of length [n+1].

While n is min(string1.length,string2.length)

code in C++:

int LCS_SpaceOptimized(string s1, string s2){
	int n = min(s1.length(),s2.length());
	int curr[n + 1];
	int prev[n + 1];

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (i == 0 || j == 0)
				curr[j] = 0;

			else if (s1[i - 1] == s2[j - 1])
				curr[j] = prev[j - 1] + 1;

			else
				curr[j] = max(prev[j], curr[j - 1]);
		}
		for (int k = 0; k < n + 1; k++)
			prev[k] = curr[k];

	}
	return curr[n];
}