D. Slavic's Exam
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
Slavic has a very tough exam and needs your help in order to pass it. Here is the question he is struggling with:
There exists a string \(s\), which consists of lowercase English letters and possibly zero or more "?".
Slavic is asked to change each "?" to a lowercase English letter such that string \(t\) becomes a subsequence (not necessarily continuous) of the string \(s\).
Output any such string, or say that it is impossible in case no string that respects the conditions exists.
Input
The first line contains a single integer \(T\) (\(1 \leq T \leq 10^4\)) — the number of test cases.
The first line of each test case contains a single string \(s\) (\(1 \leq |s| \leq 2 \cdot 10^5\), and \(s\) consists only of lowercase English letters and "?"-s) – the original string you have.
The second line of each test case contains a single string \(t\) (\(1 \leq |t| \leq |s|\), and \(t\) consists only of lowercase English letters) – the string that should be a subsequence of string \(s\).
The sum of \(|s|\) over all test cases doesn't exceed \(2 \cdot 10^5\), where \(|x|\) denotes the length of the string \(x\).
Output
For each test case, if no such string exists as described in the statement, output "NO" (without quotes).
Otherwise, output "YES" (without quotes). Then, output one line — the string that respects all conditions.
You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", and "Yes" will be recognized as a positive response).
If multiple answers are possible, you can output any of them.
题意
给你两个字符串
第一个字符串内部可能带有问号
第二个字符串长度小于等于第一个字符串
你可以用任意字符替换第一个字符串内的问号
问：第二个字符串能不能成为第一个字符串的子序列
如果可以，请输出YES和第一个字符串（任意合法情况）
如果不行就输出NO
Example
Input
5
?????
xbx
ab??e
abcde
ayy?x
a
ab??e
dac
paiu
mom
Output
YES
xabax
YES
abcde
YES
ayyyx
NO
NO
题解
很典型的贪心题目
主要是遍历字符串去寻找子序列
用两个指针指向两个字符串的开头
- 假如
第一字符串指针 指向对象内容是?
把?替换成第二字符串指针 指向内容
两个指针一起往后移动 - 假如
第一字符串指针和第二字符串指针指向对象内容相同，
两个指针一起往后移动 - 假如
第一字符串指针和第二字符串指针指向对象内容不同
第一字符串指针往后移动
假如第一字符串遍历完之后
- 第二字符串指针还没有遍历完
就输出NO - 第二字符串指针已经遍历完
先输出YES
再输出第一字符串（剩下的问号替换成任意字母即可）
代码
#include <bits/stdc++.h>
#define int unsigned long long
#define INF 0x3f3f3f3f
#define all(x) x.begin(),x.end()
int t = 1;
void solve() {
std::string a,b;
std::cin >> a >> b;
int l1 = a.size(),l2 = b.size();
int st1 = 0,st2 = 0;
while(st1 != l1 && st2 != l2) {
if(isalpha(a[st1])) {
if(a[st1] == b[st2]) st1++,st2++;
else st1 ++;
}
else {
a[st1] = b[st2];
st1++,st2++;
}
}
if(st2 == l2) {
std::cout << "YES\n";
for(int i = 0 ; i < l1 ; i ++) std::cout << (isalpha(a[i]) ? a[i] : 'a');
std::cout << "\n";
}
else std::cout << "NO\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> t;
while(t--) solve();
return 0;
}
有什么问题/建议/意见的
可以在评论区提出！
非常欢迎！