A29399. 字母游戏
填空题
较难
知识点
题目描述
字母游戏
题目描述
一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母，只是顺序不同。换句话说，将 S 中的字母重排顺序就可以得到 T。游戏的每一步，我们可以将 S 中的任一字母移动到串头或串尾，问将 S 变换成 T 至少需要多少步？
时间限制：6000 内存限制：65536
输入
输入分两行，先后给出字母串 S 和 T。如题面所描述的，两者包含同样的小写英文字母，只是顺序不同。每个字母串的长度不超过 1000。
输出
在一行中输出将 S 变换成 T 至少需要的步骤数。
样例输入
iononmrogdg
goodmorning样例输出
8提示
样例解释：
1、 从 iononmrogdg 开始；
2、 将最后一个 g 移动到串头: giononmrogd；
3、 将 m 移动到串尾: giononrogdm；
4、 将第一个 o 移动到串尾: ginonrogdmo；
5、 将 r 移动到串尾: ginonogdmor；
6、 将第一个 n 移动到串尾: gionogdmorn；
7、 将 i 移动到串尾: gonogdmorni；
8、 将第一个 n 移动到串尾: googdmornin；
9、 将第二个 g 移动到串尾: goodmorning。
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int n = s.size();
unordered_map<char, vector<int>> pos_map;
for (int i = 0; i < n; ++i) {
pos_map[s[i]].push_back(i);
}
int max_len = 0;
for (int i = 0; i < n; ++i) {
int current_pos = -1;
int count = 0;
for (int j = i; j < n; ++j) {
char c = t[j];
if (pos_map.find(c) == pos_map.end()) {
break;
}
vector<int>& v = pos_map[c];
auto it = upper_bound(v.begin(), v.end(), current_pos);
if (it == v.end()) {
break;
}
current_pos = *it;
count++;
}
if (count > max_len) {
max_len = count;
}
}
cout << n - max_len << endl;
return 0;
}
上一题
下一题