c - C中的所有最小Levenshtein距离解

Question

我应该计算 C 中两个字符串的 Levenshtein 距离。我已经成功创建了矩阵并返回了正确的 Levenshtein 距离，但是，现在我还需要为最小 Levenshtein 距离打印所有不同的可能解决方案

我试图以递归方式执行此操作，但每次都失败。

这是我最近尝试的代码：

void printLevenshteinSolutions(int const matrix[], int rows, int cols, int r, int c, char* solution){
    
    if((r==0) && (c==0)){
        printf("Solution found:\t|%s|\n", solution);
        solutionCount++;
    }
    else{
        int currentIndex = convertMatrixIndex(r, c, cols);
        int leftIndex = convertMatrixIndex(r-1, c, cols);
        int topIndex = convertMatrixIndex(r, c-1, cols);
        int diagonalIndex = convertMatrixIndex(r-1, c-1, cols);
        char oldSolution[MAX];
        strcpy(oldSolution, solution);

        if(matrix[currentIndex] >= matrix[leftIndex]){
            if((matrix[leftIndex]<=matrix[topIndex]) && (matrix[leftIndex]<=matrix[diagonalIndex])){
                strcat(solution, "d");
                if((r-1>=0))
                    printLevenshteinSolutions(matrix, rows, cols, r-1, c, solution);
                strcpy(solution, oldSolution);
            }
        }
        if(matrix[currentIndex] >= matrix[topIndex]){
            if((matrix[topIndex]<=matrix[leftIndex]) && (matrix[topIndex]<=matrix[diagonalIndex])){
                strcat(solution, "i");
                if((c-1>=0))
                    printLevenshteinSolutions(matrix, rows, cols, r, c-1, solution);
                strcpy(solution, oldSolution);

            }
        }
        if(matrix[currentIndex] >= matrix[diagonalIndex]){
            if((matrix[diagonalIndex]<=matrix[topIndex]) && (matrix[diagonalIndex]<=matrix[leftIndex])){
                if(matrix[currentIndex] > matrix[diagonalIndex]){
                    strcat(solution, "c");
                }
                else{
                    strcat(solution, " ");
                }
                if((c-1>=0)&&(r-1>=0))
                    printLevenshteinSolutions(matrix, rows, cols, r-1, c-1, solution);
                strcpy(solution, oldSolution);
            }
        }

    }
}

现在这将以错误的方式输出解决方案，我可以修复它，但更大的问题是解决方案根本不正确。

更新:: 我正在尝试计算从矩阵右下角到左上角的可能路径。我不只是想要任何路径！从一个单元到另一个单元的任何连接都必须向左、上或左上

此外，它还必须只达到这三个相邻单元格的最小值。

例如：

012
134
234

在这里，底部 4 必须与其左侧的 3 连接，以获得一种可能的解决方案。它还必须连接到对角线左侧的 3，以获得另一种可能的解决方案。它不能包括从底部 4 到顶部 4 的路径，因为 4 > 3

标签： crecursionlevenshtein-distance