给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。 输入格式: 第一行包含两个整数N和M。1≤N,M≤1000 第二行包含一个长度为N的字符串,表示字符串A。 第三行包含一个长度为M的字符串,表示字符串B。 字符串均由小写字母构成。 输出格式: 输出一个整数,表示最大长度。用java代码实现
时间: 2024-03-05 15:48:06 浏览: 195
以下是 Java 语言的实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
String A = scanner.next();
String B = scanner.next();
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i-1) == B.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
System.out.println(dp[n][m]);
}
}
```
代码中使用了动态规划的思想,`dp[i][j]` 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符中既是 A 的子序列又是 B 的子序列的字符串的最大长度。当 A[i-1] == B[j-1] 时,说明字符串 A 的第 i 个字符和字符串 B 的第 j 个字符相同,此时最大长度为 dp[i-1][j-1] + 1;否则最大长度为 dp[i-1][j] 和 dp[i][j-1] 中的最大值。最终的最大长度即为 `dp[n][m]`。
时间复杂度为 O(NM),空间复杂度为 O(NM)。
阅读全文