CF1553 D. Backspace（贪心）

目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

有两个字符串 s t ，s 中的每个字符都可以当作 Backspace ，即删掉前一个字符（如果前面存在字符的话），问是否可以将 s 串变为 t 串

State

测试样例 \(1<=q<=10^5\)

\(1<=|s|<=10^5\)

\(1<=|t|<=10^5\)

Input

4
ababa
ba
ababa
bb
aaa
aaaa
aababa
ababa

Output

4
ababa
ba
ababa
bb
aaa
aaaa
aababa
ababa

Solution

在保留下一个字符之前，我们可以删除任意个数的字符，之后只能一次性删除两个字符，所以不妨倒着删，剩下的部分一直按 Backspace 键即可

Code

signed main()
{
    IOS;
    rush(){
        string s, t;
        cin >> s >> t;
        int i = s.size() - 1, j = t.size() - 1;
        for(; i >= 0;){
            if(s[i] == t[j]){
                j --;
                i --;
            }
            else{
                i -= 2;
            }
            if(j == -1) break;
        }
        puts(j == -1 ? "YES" : "NO");
    }
    return 0;
}