Levenshtein Distance算法

优化空间复杂度由O(mn)到O(min(n,m))。

function levenshtein(s, t){
	if (s === t){
		return 0;
	}
	var m = s.length, n = t.length;
	if (!m || !n){
		return Math.max(m,n);
	}
	if (m < n){
		var tmp = s;
		s = t;
		t = tmp;
		tmp = m;
		m = n;
		n = tmp;
		tmp = null;
	}

	var d = [], i,j;

	for (j = 0; j <= n; j++){
		d[j] = j;
	}

	var pre, tmp, _s;
	for (i = 0; i < m; i++){
		_s = s.charAt(i);
		pre = i + 1;
		for (j = 0; j < n ; j++){
			tmp = d[j];
			d[j] = pre;
			pre = (_s === t.charAt(j) ? tmp : 1 + Math.min(pre , Math.min(d[j+1], tmp)));
		}
		d[j] = pre;
	}

	return pre;
}

ps：PHP竟然将这个算法内置了...