1

我正在尝试解决编辑距离问题。我一直在使用的代码如下。

 public static int minDistance(String word1, String word2) {
    int len1 = word1.length();
    int len2 = word2.length();

    // len1+1, len2+1, because finally return dp[len1][len2]
    int[][] dp = new int[len1 + 1][len2 + 1];

    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }

    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }

    //iterate though, and check last char
    for (int i = 0; i < len1; i++) {
        char c1 = word1.charAt(i);
        for (int j = 0; j < len2; j++) {
            char c2 = word2.charAt(j);

            //if last two chars equal
            if (c1 == c2) {
                //update dp value for +1 length
                dp[i + 1][j + 1] = dp[i][j];
            } else {
                int replace = dp[i][j] + 1 ;
                int insert = dp[i][j + 1] + 1  ;
                int delete = dp[i + 1][j] + 1 ;


                int min = replace > insert ? insert : replace;
                min = delete > min ? min : delete;
                dp[i + 1][j + 1] = min;
            }
        }
    }

    return dp[len1][len2];
}

这是一种DP方法。问题在于它使用二维数组，我们无法使用上述方法解决大字符串的问题。例如：字符串长度 > 100000。

那么有没有办法修改这个算法来克服这个困难呢？

注意：上面的代码将准确地解决小字符串的编辑距离问题。（长度小于 1000 或接近）

正如您在代码中看到的，它使用 Java 2D 数组 "dp[][]" 。所以我们不能为大的行和列初始化一个二维数组。

例如：如果我需要检查 2 个长度超过 100000 的字符串

int[][] dp = new int[len1 + 1][len2 + 1];

以上将是

int[][] dp = new int[100000][100000];

所以它会给出一个stackOverflow错误。

所以上面的程序只适用于小长度的字符串。我要问的是，有没有办法在java中有效地解决大字符串（长度> 100000）的这个问题。

4

1 回答 1

2

首先，在 Java 中分配 100k x 100k int 数组没有问题，您只需要在堆中进行，而不是在堆栈中（并且在具有大约 80GB 内存的机器上 :)）

其次，作为（非常直接的）提示：

请注意，在您的循环中，您一次只能使用 2 行 - rowi和 row i+1。实际上，您i+1从 row 计算 row i。一旦你得到i+1你就不需要再存储 rowi了。

这个巧妙的技巧允许您同时仅存储 2 行，从而将空间复杂度从 降低n^2到n. 既然你说这不是家庭作业（即使你的个人资料是 CS 本科生......），我相信你会自己想出代码。

回想一下，我记得我在 CS 学位课程中遇到过这个确切的问题......

于 2014-10-06T10:39:14.447 回答