Java 中查找最长公共子字符串的长度 - 时间和空间复杂度分析

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;

}

以上算法的时间和空间复杂度是多少

时间复杂度：O(m * n)，其中 m 为 str1 的长度，n 为 str2 的长度。因为算法使用了两重循环，每次循环都需要常数时间，所以总的时间复杂度是 O(m * n)。

空间复杂度：O(m * n)，其中 m 为 str1 的长度，n 为 str2 的长度。因为算法使用了一个二维数组 dp，其大小为 (str1.length() + 1) * (str2.length() + 1)，所以总的空间复杂度是 O(m * n)。