题意:在字符串S中找到字符串T并将其删除,删除之后如果又合并出一个新的字符串T,则还要将其删除。
一开始感觉是用KMP,但发现KMP貌似不能连续删除,那该怎么办呢?(其实当时我不会KMP,hahaha)
又看了看题,感觉这个东西跟消消乐有点差不多,便让我想起了一个数据结构——栈。
每读取一个字符,就把它压到栈里,一旦栈顶的字符串等于T,就把它们全部弹掉,用Hash比较一下就行了。
模拟一下样例:
栈 当前字符
whatthemomo o
此时把o压到栈里
whatthemomoo o
发现栈顶3个元素的hash值等于T的hash值,弹栈
whatthemo o
再把下一个字符压到栈里
whatthemoo o
又发现栈顶3个元素的hash值等于T的hash值,再弹栈
whatthe o
这样一直扫下去就好了
这道题还是很简单的,主要是很有意思,有一种玩消消乐的感觉。
AC代码
欢迎加入团队