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

在这个问题中,我们可以使用两个大小为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,也不会导致堆溢出

public static int findMaxCommonSubstringLengthString str1 String str2 int dp = new intstr1length + 1str2length + 1; int maxLength = 0; for int i = 1; i = str1length;

原文地址: https://www.cveoy.top/t/topic/iG4A 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录