Фирма "1С". "Алгоритмы. Олимпиадное программирование на языке Java для школьников"

static int memo[][];
public static int levenshtein(String word1, String word2)
{
	int len1 = word1.length();
	int len2 = word2.length();
	memo = new int[len1 + 1][len2 + 1];
	for (int i = 0; i <= len1; i++)
	{
		memo[i][0] = i;
	}
	for (int i = 0; i <= len2; i++)
	{
		memo[0][i] = i;
	}
	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			if (word1.charAt(i - 1) == word2.charAt(j - 1))
			{
				memo[i][j] = memo[i - 1][j - 1];
			}
			else
			{
				int insert = memo[i][j - 1] + 1;
				int remove = memo[i - 1][j] + 1;
				int replace = memo[i - 1][j - 1] + 1;
				if ((insert <= remove) && (insert <= replace))
				{
					memo[i][j] = insert;
				}
				else if ((remove <= insert) && (remove <= replace))
				{
					memo[i][j] = remove;
				}
				else if ((replace <= remove) && (replace <= insert))
				{
					memo[i][j] = replace;
				}
			}
		}
	}
	// result
	int result = memo[len1][len2];
	return result;
}