Skip to content

Latest commit

 

History

History
 
 

936.Stamping-The-Sequence

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

936.Stamping-The-Sequence

周赛的时候想到的是递归。对于这一系列stamp的操作,只关注最后一次盖章:其实可以看成找到中间某处完全匹配的地方,将整个序列断成了两部分,能匹配的部分我们就替换成是"*****".这样我们将原来的问题分解为了两个子序列,可以再递归处理。其中如果遇到边界是星号的部分我们都认为能匹配上的。

其实上面的想法再进一步的话,可以得到更优美的贪心解法。

思想本质是:我们只要在当前的target中能够找到匹配stamp的片段,比如说是区间[a,b],我们就将标记这个操作为最后一步操作。然后无论我们怎么处理剩下的序列,当我们回过头来最终执行替换[a,b]的操作时,都能保证[a,b]是正确的。也就是说,无论怎么折腾剩下的,最终都不会影响[a,b]。同理,如果我们再在剩下的target里中能找到匹配stamp的片段,比如说[c,d]时,我们就将其标记为倒数第二次操作,那么无论再之后的操作如何,最终都不会影响[c,d]以及[a,b]。

举个例子:

target:
XXXXabcabcdcdXXX

operations:
#N-0: XXXXXXXabcdXXXXX
#N-1: XXXXabcd***XXXXX
#N-2: XXXXXXX**abcdXXX
...

当从下往上执行最后三步替换之后,一定能保证序列最终中间的部分是期望的abcabcdcd.原因在于,后面的操作会覆盖前面的操作,所以前面的操作(比如说第N-1次)只需要负责后面操作(第N次)覆盖不到的那部分即可(i.e. abc),其他的反正都会被后面的操作覆盖(i.e. d),当前的替换即使不正确也没关系。

所以我们的策略是从上往下,只要能在当前序列中能找到匹配的,我们就将其置为星号。然后再剩下的序列里,只要能找到匹配的(其中如果序列中已经有星号则视为任意匹配),我们也立即将其置为星号。直至序列中所有的字符都已经置为星号为止。注意,最终的操作顺序则是反过来。