抱歉,长标题:)
在这个问题中,我们有S长度的n字符串T和长度的字符串m.我们可以在时间复杂度O(n + m)中检查字符串S的子序列T.这很简单.
我很好奇:如果我们可以删除最多K连续的字符怎么办？例如,如果K = 2,我们可以"ab"从"accb",但不从"abcccb".我想检查它是否可能非常快.
我只能发现很明显O(nm):检查字符串S和字符串中的每个后缀对是否可能T.我认为也许贪婪的算法是可能的,但如果K = 2,情况S = "abc"并且T = "ababbc"是一个反例.
有没有解决这个问题的快速解决方案？
小智 0
不确定这是否是您所要求的，但您可以从每个字符串创建一个字符列表，并在另一个列表中搜索一个列表的实例，然后 if(list2.length-K > list1.length) 返回 false。