用java实现现在有两个字符串S和T,你需要对S进行若干次操作,使得S是T的一个前缀(空串也是一个前缀)。每次操作可以修改S的一个字符,或者删除一个S末尾的字符。 小团需要写一段程序,输出最少需要操作的次数
时间: 2024-02-27 17:59:24 浏览: 33
好的,这是一个比较经典的字符串问题,可以使用动态规划算法来解决。以下是Java代码实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String t = sc.nextLine();
int n = s.length();
int m = t.length();
int[][] dp = new int[n + 1][m + 1]; // dp[i][j]表示s的前i个字符和t的前j个字符匹配的最小操作次数
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0) {
dp[i][j] = j; // s为空串,需要对t进行j次操作
} else if (j == 0) {
dp[i][j] = i; // t为空串,需要对s进行i次操作
} else if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // s和t的末尾字符相同,不需要操作
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1; // s和t的末尾字符不同,需要进行一次操作
}
}
}
System.out.println(dp[n][m]); // 输出最少需要操作的次数
}
}
```
输入格式:
第一行包含一个字符串S。
第二行包含一个字符串T。
输出格式:
输出最少需要操作的次数。
希望对你有帮助!