我用 java 实现了 Wagner Fischer 算法，但我想显示所有步骤。 我搜索但找不到任何想法。很长一段时间后，我试图将每个转换与成本一起保存在矩阵中，然后回到第一个解决方案然后反转它......这是一个好主意，如果是，应该如何我设置条件？

kitten -> sitting
1.replace k with s
2.keep i
3.keep t
4.keep t
5.replace t
6.add g

我试图为显示步骤创建函数，但不知道如何解决。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Principal {
    static int c1, c2, c3;
    static String word1, word2;

    public  static void main(String[] args) throws FileNotFoundException {
        Scanner data_in = new Scanner(new File("data.in"));
        word1 = data_in.next();
        word2 = data_in.next();
        c1 = data_in.nextInt();
        c2 = data_in.nextInt();
        c3 = data_in.nextInt();

        System.out.printf("\nInsert: %s, Delete: %s, Replace: %s\n", c1, c2, c3);

        System.out.printf("\nLevenstheinDistance: %s", LevenshteinDistance(word1, word2, c1, c2, c3));
    }

    private static int LevenshteinDistance(String str1, String str2, int InsCost, int DelCost, int ReplCost)
    {
        if(word1.length() == 0)
            return InsCost*str1.length();
        if(word2.length() == 0)
            return DelCost*str2.length();

        int substitutionCost = ReplCost;
        if(ReplCost > InsCost + DelCost)
            ReplCost = InsCost + DelCost;

        Solution[][] ManageSol = new Solution[str1.length()+1][str2.length()+1];

        for(int i = 0; i <= str1.length(); i++)
        {
            for(int j = 0; j <= str2.length(); j++){
                ManageSol[i][j] = new Solution();
            }
        }

        System.out.printf("\nLungime str1: %s", str1.length());
        System.out.printf("\nLungime str2: %s", str2.length());

        for(int i = 0; i <= str1.length(); i++)
        {
            for (int j = 0; j <= str2.length(); j++)
            {
                if (i == 0)
                    ManageSol[i][j].solution = j;
                else if (j == 0)
                    ManageSol[i][j].solution = i;
                else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                {
                    substitutionCost = 0;
                    ManageSol[i][j].ecqualTo(minimum(
                            ManageSol[i][j - 1].solution + InsCost,
                            ManageSol[i - 1][j].solution + DelCost,
                            ManageSol[i - 1][j - 1].solution + substitutionCost));
                    System.out.printf("\nManagerSol[%s, %s]: ch1: %s, ch2: %s", i, j, str1.charAt(i - 1), str2.charAt(j - 1));
                }
                else
                {
                    substitutionCost = 1;
                    ManageSol[i][j].ecqualTo(minimum(
                            ManageSol[i][j - 1].solution + InsCost,
                            ManageSol[i - 1][j].solution + DelCost,
                            ManageSol[i - 1][j - 1].solution + substitutionCost));
                    System.out.printf("\nManagerSol[%s, %s]: ch1: %s, ch2: %s", i, j, str1.charAt(i - 1), str2.charAt(j - 1));
                }
            }
        }

        System.out.printf("\n");
        path(ManageSol, str1.length(), str2.length(), str1, str2);
        System.out.printf("\n");

        for(int i = 0; i <= str1.length(); i++)
        {
            for (int j = 0; j <= str2.length(); j++)
            {
                System.out.printf("[%s,%s]:(%s,%s) ", i, j, ManageSol[i][j].solution, ManageSol[i][j].operation);
            }
            System.out.printf("\n");
        }

        return ManageSol[str1.length()][str2.length()].solution;
    }

    static int minimum(int x, int y)
    {
        if(x >= y)
            return x;
        return y;
    }

    static Solution minimum(int Ins, int Del, int Replace)
    {

        Solution solution = null;
        if(Ins <= Del && Ins <= Replace)
        {
            solution = new Solution();
            solution.operation = 1;
            solution.solution = Ins;
            return solution;
        }
        else if(Del <= Ins && Del <= Replace)
        {
            solution = new Solution();
            solution.operation = 2;
            solution.solution = Del;
            return solution;
        }
        else
        {
            solution = new Solution();
            solution.solution = Replace;
            solution.operation = 0;
            return solution;
        }
    }

    //my failure, function that should display steps
    static void path(Solution[][] ManagerSol, int i, int j, String str1, String str2)
    {
        if(ManagerSol[i][j].operation == 0)
        {
            System.out.printf("\nReplace %s -> %s", str1.charAt(i-1), str2.charAt(j-1));
            if(i > 1 && j > 1)
                path(ManagerSol, i-1,j-1, str1, str2);
        }
        if(ManagerSol[i][j].operation == 1)
        {
            System.out.printf("\nAdd %s on position %s", str2.charAt(j-1), i-1);
            if(j > 1)
                path(ManagerSol, i,j-1, str1, str2);
        }
        if(ManagerSol[i][j].operation == 2)
        {
            System.out.printf("\nDelete %s", str1.charAt(i-1));
            if(j > 1)
                path(ManagerSol, i-1,j, str1, str2);
        }
    }
}

小猫坐下的输出:

[0,0]:(0,3) [0,1]:(1,3) [0,2]:(2,3) [0,3]:(3,3) [0,4]:(4,3) [0,5]:(5,3) [0,6]:(6,3) [0,7]:(7,3) 
[1,0]:(1,3) [1,1]:(1,0) [1,2]:(2,1) [1,3]:(3,1) [1,4]:(4,1) [1,5]:(5,1) [1,6]:(6,1) [1,7]:(7,1) 
[2,0]:(2,3) [2,1]:(2,2) [2,2]:(1,0) [2,3]:(2,1) [2,4]:(3,1) [2,5]:(4,1) [2,6]:(5,1) [2,7]:(6,1) 
[3,0]:(3,3) [3,1]:(3,2) [3,2]:(2,2) [3,3]:(1,0) [3,4]:(2,1) [3,5]:(3,1) [3,6]:(4,1) [3,7]:(5,1) 
[4,0]:(4,3) [4,1]:(4,2) [4,2]:(3,2) [4,3]:(2,2) [4,4]:(1,0) [4,5]:(2,1) [4,6]:(3,1) [4,7]:(4,1) 
[5,0]:(5,3) [5,1]:(5,2) [5,2]:(4,2) [5,3]:(3,2) [5,4]:(2,2) [5,5]:(2,0) [5,6]:(3,1) [5,7]:(4,1) 
[6,0]:(6,3) [6,1]:(6,2) [6,2]:(5,2) [6,3]:(4,2) [6,4]:(3,2) [6,5]:(3,2) [6,6]:(2,0) [6,7]:(3,1) 

最佳答案

总的来说你的想法是正确的。它甚至比那更简单。您不需要存储任何其他信息。

您可以向后(从给定字符串的末尾开始)并按以下方式使用您的动态编程值:

1. 如果其中一个索引为 0，则只有一条路可走。

2. 否则，您可以“向后”查看 3 种可能的转换(从 (i, j) 到 (i - 1, j - 1)、(i - 1, j) 和 (i, j - 1 )) 并选择产生 (i, j) 实际值的那个。如果有多个可能的选项，您可以选择其中的任何一个。

一旦您知道从给定的一对位置到哪里去，操作就唯一确定了。

关于java - Wagner Fischer算法+展示步骤，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41432675/