java - 大きな文字列の距離ソリューションを編集

Question

編集距離の問題を解決しようとしています。私が使用しているコードは以下のとおりです。

 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アプローチです。2D配列を使用しているため、大きな文字列に対して上記の方法を使用してこの問題を解決することはできません。例: 文字列の長さ > 100000。

それで、その困難を克服するためにこのアルゴリズムを変更する方法はありますか?

注: 上記のコードは、小さな文字列の編集距離の問題を正確に解決します。(長さが 1000 未満またはそれに近い)

コードでわかるように、Java 2D Array "dp[][]" を使用しています。したがって、大きな行と列の 2D 配列を初期化することはできません。

例：長さが100000を超える2つの文字列をチェックする必要がある場合

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

上記は

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

そのため、stackOverflow エラーが発生します。

したがって、上記のプログラムは、長さが短い文字列にのみ適しています。私が求めているのは、Javaで大きな文字列（長さ> 100000）のこの問題を効率的に解決する方法はありますか.