java - 从 Levenshtein 距离获取每一步

Question

我有一个 Java 程序，可以计算两个字符串之间的编辑距离。我用这个方法来做:

    public static int levDistance(String s, int len_s, String t, int len_t) {
        if (len_s == 0)
            return len_t;
        if (len_t == 0)
            return len_s;

        int cost = 0;
        if (s.charAt(len_s - 1) == t.charAt(len_t - 1))
            cost = 0;
        else
            cost = 1;
        return Math.min(Math.min(
                levDistance(s, len_s - 1, t, len_t) + 1,
                levDistance(s, len_s, t, len_t - 1) + 1),
                levDistance(s, len_s - 1, t, len_t - 1) + cost);
}

正如标题所示，我需要完成此过程中的每一步。我并不关心它是如何返回的(可以是换行符分隔的，在数组列表中等)或者它的顺序是什么，只关心每一步都会更改一个字符。

示例:

distance("saturday", "sauterdai"); -> "saturday", "sauterday", "sauterdai"
distance("algorithm", "algurthm") -> "algorithm", "algorthm", "algurithm"
distance("stackoverflow", "mathoverflow") -> "stackoverflow", "tackoverflow", "tckoverflow", "tkoverflow", "toverflow", "mtoverflow", "matoverflow", "mathoverflow"

Answer 1

在递归完成之前，您无法确定给定的更改是否位于实际路径中。这是解决这个问题的一种策略:

定义一个捕获 List<String> 的数据结构以及使用该列表作为更改链的整数成本。制作levDistance返回对该数据结构实例的引用。

在基本情况下，列表仅包含原始的两个字符串。对于非基本情况，展开最小值的计算，并为所选情况填写新的中间字符串。