public static int findMaxCommonSubstringLengthString str1 String str2 int dp = new intstr1length + 1str2length + 1; int maxLength = 0; for int i = 1; i = str1length;
为了减少空间占用,可以使用滚动数组的技巧。滚动数组是一种优化技术,用于减少动态规划中使用的数组的大小,从而节省内存空间。
在这个问题中,我们可以使用两个大小为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,也不会导致堆溢出
原文地址: https://www.cveoy.top/t/topic/iG4A 著作权归作者所有。请勿转载和采集!