1553-D, *1500

Problem - 1553D - Codeforces

문제

• 문자열 $s$와 $t$가 주어진다
• $s$의 왼쪽부터 문자 하나당 시행1 이나 시행2를 한다
  시행1. 키보드로 그 문자를 누른다
  시행2. 키보드로 그 문자를 누르지 않고 Backspace 를 누른다
  ex) abcd 에서 순차적으로 1121 시행했다면 $\mathrm{a\rightarrow ab \rightarrow a\rightarrow ad}$
       abdd 에서 순차적으로 2121 시행했다면 $\ \rightarrow b \rightarrow \  \rightarrow d$
• $s$로 부터 $t$를 작성할 수 있는가?

 

$O(\left | s \right |)$ 

$sp,\ tp$ 두개의 포인터를 사용하여 $t$의 뒤쪽부터 앞쪽으로가며 시뮬레이션 해본다

두 포인터의 값이 같으면 시행1을 하면되며, 같이 않으면 시행2를 하면 되겠다

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
string s, t;
int sp, tp;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int tc;
    cin >> tc;
    while(tc--){
        cin >> s >> t;
        sp = s.size()-1;
        tp = t.size()-1;
 
        while(sp >= 0 && tp >= 0){
            if(s[sp] == t[tp]){
                sp--;
                tp--;
            }
            else sp -= 2;
        }
 
        cout << ((tp == -1)? "YES": "NO") << endl;
 
    }
 
    return 0;
}cs