优化寻找最长公共子字符串长度算法：滚动数组技巧

以下代码是寻找两个字符串的最长公共子字符串长度的算法。

public static int findMaxCommonSubstringLength(String str1, String str2) {
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    int maxLength = 0;

    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
    }

    return maxLength;
}

当字符串长度很大时，例如 3000，3000 * 3000 的数组会让堆溢出。为了减少空间占用，可以使用滚动数组的技巧。

滚动数组是一种优化技术，用于减少动态规划中使用的数组的大小，从而节省内存空间。

在这个问题中，我们可以使用两个大小为 str2.length() + 1 的一维数组，而不是一个大小为 (str1.length() + 1) * (str2.length() + 1) 的二维数组。每次计算 dp[i][j] 时，只需要使用当前行和上一行的数组值，而不需要保留整个二维数组。

以下是修改后的代码：

public static int findMaxCommonSubstringLength(String str1, String str2) {
    int[] prevRow = new int[str2.length() + 1];
    int[] currentRow = new int[str2.length() + 1];
    int maxLength = 0;

    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                currentRow[j] = prevRow[j - 1] + 1;
                maxLength = Math.max(maxLength, currentRow[j]);
            }
        }
        // 更新 prevRow 数组为 currentRow 数组
        for (int j = 0; j <= str2.length(); j++) {
            prevRow[j] = currentRow[j];
        }
    }

    return maxLength;
}

通过使用滚动数组，我们只需要存储当前行和上一行的数组值，从而将空间复杂度从 O(str1.length() * str2.length()) 降低到 O(str2.length())。这样即使字符串长度为 3000，也不会导致堆溢出。