欢迎访问==> 【考研OR保研】机试题
题目描述
给定一个由大写字母构成的字符串 $s$。
字符串 $s$ 中的若干个(也可能没有)字符缺失了,缺失的字符用 ?
表示。
现在,请你将字符串进行补全,即将字符串中的每个 ?
字符都替换为一个任意大写字母(A
- Z
)。
要求,补全后的字符串至少包含一个长度为 $26$ 的连续子串,在该子串中,每个大写字母恰好出现一次。
输入格式
共一行,一个字符串 $s$,其中的每个字符都是大写字母(A
- Z
)或问号(?
)。
输出格式
如果不存在合理的补全方案,得到满足条件的完整字符串,则输出 $\-1$。
如果存在合理的补全方案,则输出补全后的字符串。
如果方案不唯一,输出任意合理方案均可。
数据范围
前 $6$ 个测试点满足 $1 \\le |s| \\le 100$。
所有测试点满足 $1 \\le |s| \\le 50000$。
输入样例1:
ABC??FGHIJK???OPQR?TUVWXY?
输出样例1:
ABCDEFGHIJKLMNOPQRZTUVWXYS
输入样例2:
ABCDEFGHIJKLMNOPQRSTUVWXY
输出样例2:
-1
输入样例3:
??????????????????????????
输出样例3:
MNBVCXZLKJHGFDSAQPWOEIRUYT
输入样例4:
AABCDEFGHIJKLMNOPQRSTUVW??M
输出样例4:
-1
C++ 代码
/*
从头到尾扫描一遍,检查每一段长度为26的子串
如果里面存在相同的字符,跳过这段继续检查下一个子串
如果里面不存在相同的字符,则可以成为答案
*/
#include <bits/stdc++.h>
using namespace std;
string s;
unordered_set<char> h;
vector<char> t;
int main()
{
cin >> s;
//枚举子串的起始位置
for(int i = 0; i + 25 < s.size(); i ++)
{
h.clear();
t.clear();
bool flag = true;
//枚举每一段26字符的子串
for(int j = i; j < i + 26; j ++)
{
if(s[j] == '?') continue;
if(!h.count(s[j])) h.insert(s[j]);
else {flag = false; break;}
}
if(flag)
{
for(char j = 'A'; j <= 'Z'; j ++)
{
if(!h.count(j)) t.push_back(j);
}
for(int j = i; j < i + 26; j ++)
{
if(s[j] == '?')
{
s[j] = t.back();
t.pop_back();
}
}
for(int j = 0; j < s.size(); j ++)
{
if(s[j] == '?') s[j] = 'A';
}
cout << s << endl;
return 0;
}
}
puts("-1");
return 0;
}