算法题记录 - 键盘测试

第一行是一个整数 q (1≤q≤10^5），代表测试用例的数量。
每个测试用例的第一行是字符串s (1≤s的长度≤10^5)，s中的每个字符是小写的英文字母。
每个测试用例的第二行是字符串t (1≤t的长度≤10^5)，t中的每个字符是小写的英文字母。

对于每个测试用例，如果可以按本题的方式从s得到t，请打印”YES“,否则，打印“NO”。

1
2
3
4
5
6
7
8
9

4
ababa
ba
ababa
bb
aaa
aaaa
aababa
ababa

1
2
3
4

YES
NO
NO
YES

看到题目首先观察了 s 和 t 的联系。首先的想法如下：

• 对于 s，首先寻找其中所包含的第一个 t[0]。如果没有 t[0]，那么肯定无法输出。
• 如果有 t[0]，接着去找 t[1]，看看两个字母之间的字母数是不是偶数个（打出，删除，打出，删除…）。如果不是，那么肯定无法输出。
• 如果还是，那么继续重复以上的步骤，直到 t 越界。

遇到的问题：

• aababa 和 ababa 无法处理。说明如果 s 存在 t[0]，但完全无效，则应该去除 s 中 t[0] 即其之前的部分，重新进行测试。但是此方法只适用于 t[0]，因为实际上在符合要求的 t[0] 于 s 中出现之前，用户可以什么都不输入只按退格键。并且，这样的方法对于大数据来说太慢了。
• 本身的算法就非常难设计，需要三个指针，两个位于 s 标定位置，一个位于 t 指向当前的内容。

反向思考，如果说开头的东西可以忽视会让人难以处理，那么把开头放在最后就好了。同时，我们知道符合要求的字符串 s 的尾部要么和 t 完全一致，要么最后相差偶数个。所以最终的设计是，从 s 和 t 的尾部开始遍历，如果相同就同时前进 1 个字母，再比较；如果不同，则 s 前进2 个字母，再比较。直到 s 或 t 某个字符串结束。最后再判断 t 有没有结束。如果 t 结束了，那么答案就是 YES，此时 s 最开始的部分就是那些我们可以只按退格键的字符。

Python 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def special_typing():
    stringNum = eval(input())

    while(stringNum != 0):
        stringS = list(input())
        stringT = list(input())

        comparePointer = len(stringS) - 1
        current = len(stringT) - 1
        while(current >= 0) and (comparePointer >= 0):
            if(stringT[current] == stringS[comparePointer]):
                current -= 1
                comparePointer -= 1
            else:
                comparePointer -= 2

        if(current < 0):
            print("YES")
        else:
            print("NO")
        
        stringNum -= 1