levenstain.cs

/*      _l1, _l2 - длины строк
        _s1, _s2 - строки
        решение было оформлено как объект с функцией
*/
        
        public int Solution()
        {
            // equal(i, j) то же самое, что m(S1[i],S2[j])
            // и равна нулю, если символы равны и единице, если иначе
            var equal = new Func<int, int, int>((x, y) => (_s1.Substring(x-1, 1) == _s2.Substring(y-1, 1)) ? 0 : 1);
            // Проверка на пустые строки
            if (_l1 == 0 && _l2 == 0) return 0;
            if (_l1 == 0) return _l2;
            if (_l2 == 0) return _l1;

            // Инициализация и заполнение матрицы
            var matrix = new int[_l1 + 1, _l2 + 1];
            for (var i = 0; i <= _l1; i++) matrix[i, 0] = i;
            for (var j = 0; j <= _l2; j++) matrix[0, j] = j;

            //Вычисление расстояния Дамерау-Левенштейна
            for (int i = 1; i <= _l1; i++)
            {
                for (int j = 1; j <= _l2; j++)
                {
                    // добавление. D(i, j-1) + 1
                    int ins = matrix[i, j - 1] + 1;

                    // удаление. D(i-1,j) + 1
                    int del = matrix[i - 1, j] + 1; 
                    
                    // замена. D(i-1, j-1) + m(S1[i],S2[j])
                    int subst = matrix[i - 1, j - 1] + equal(i, j); 

                    // элемент матрицы вычисляется как минимальный из трех случаев
                    matrix[i, j] = new List<int>{ins, del, subst}.Min();

                    // дополнение Дамерау по перестановке соседних символов
                    if ((i > 1) && (j > 1) && equal(i, j-1) == 0 && equal(i-1, j) == 0)
                        matrix[i, j] = Math.Min(matrix[i, j], matrix[i - 2, j - 2] + equal(i, j));
                   
                    // завершение обработки по достижению максимального расстояния
                    if (_max != 0 && matrix[_l1, _l2] > _max)
                        return _max + 1;
                }
            }
            return matrix[_l1, _l2];
        }