CF1553D Backspace
说实话这题不配绿题
题面
给你两个字符串 \(S,T\) ,问你能否通过将 \(S\) 中的若干个数换成 Backspace
来使其变成 \(T\) 。Backspace
能删去前一个输入的字符。
思路
很明显,如果将一个字符换成Backspace
,那么消失的就是两个连续的字母
所以,可以发现,从第零个位置到第若干个位置,都是可以被删除的,举个例子,abcde
中,假如我想删除前\(3\)个,那么只需要把前三个都换成Backspace
即可
但是如果在中间的某一个字母换成Backspace
,就一定会删除两个字母,比如abcde
中c
变为Backspace
,那么消失的是bc
假如连续两次在中间的位置按下Backspace
,其实本质上和上述情况都是一样的,更多次也同样
所以只需要遍历\(s\),寻找\(t\),同时每次都要删除两个位置
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=1e5+10;
int now;
int lena,lenb;
string a,b;
void run()
{
cin>>a>>b;now=0;
lena=a.size(),lenb=b.size();
for(int i=(lena%2!=lenb%2);i<lena && now<lenb;i++)
{
if(b[now]==a[i]) now++;
else i++;
}
cout<<(now==lenb?"Yes":"No")<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) run();
system("echo. & pause");
return 0;
}