你的儿子小明打字水平有限,当他希望打出某个单词如 smart 时,他会错误地按到键盘上其他字母,例如形成 asnmaaaert 这样的尴尬情况。更加令人崩溃的是,小明还不会用"退回"键或者删除功能来清理错误字母。现在小明从一个词汇表里挑了若干个单词进行打字,词汇表里的所有n个单词都已知。请你识别出小明至少打错了几个字符? 换句话说,也就是去掉至少几个字符,可以使剩下的内容由词汇表里的真单词拼写出来? 输入输出格式 输入格式 输入文件typist2.in 先输入一行为正整数n和L,代表真的单词数,以及小明打了L个字符。n<=1000 第二行字符串,代表小明的打字内容,都由小写字母组成。长度不超过1000 之后共n行,每行一个英文单词,都由小写字母组成。长度均不超过1000。 输出格式 输出文件typist2.out 输出共一行,为一个整数。 输入输出样例 输入样例#1: 3 12 helllowordld hello world word 输出样例#1: 2 求正确代码
时间: 2024-04-12 07:29:30 浏览: 199
小明打字_链表的应用_源码
以下是一个可以解决这个问题的代码示例:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("typist2.in", "r", stdin);
freopen("typist2.out", "w", stdout);
int n, L;
cin >> n >> L;
string input;
cin >> input;
vector<string> wordList(n);
for (int i = 0; i < n; ++i) {
cin >> wordList[i];
}
vector<vector<int>> dp(n + 1, vector<int>(L + 1, 0));
for (int i = 1; i <= n; ++i) {
dp[i][0] = i;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= L; ++j) {
if (wordList[i - 1][j - 1] == input[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
cout << dp[n][L];
return 0;
}
```
这段代码使用了动态规划的思想来解决问题。首先,创建一个二维数组dp,其中dp[i][j]表示将输入的前j个字符变为词汇表中的前i个单词所需的最小操作次数。初始化dp的第一行和第一列,表示将空字符串变为词汇表中的前i个单词或者将输入的前j个字符变为空字符串所需的操作次数。
然后,使用两层循环遍历词汇表和输入的字符,对于每个位置(i, j),如果词汇表中的第i个单词的第j个字符与输入的第j个字符相等,则dp[i][j]等于dp[i-1][j-1],表示不需要操作。如果不相等,则dp[i][j]等于dp[i-1][j]和dp[i][j-1]中较小的值加1,表示选择删除或插入当前字符产生最小操作次数。
最后,输出dp[n][L]即为最终结果,即将输入的所有字符变为词汇表中的所有单词所需的最小操作次数。
注意:该代码是根据题目描述进行编写的,可能与你之前提供的代码有所差异。请测试该代码,如果有任何问题请及时反馈。
阅读全文