首页 > 代码库 > {CSDN}{英雄会}{反相互}

{CSDN}{英雄会}{反相互}

思路:

给定一个字符串,求两个不重叠的字串,他们翻转互补。其中一个字符串可以是删掉最多两个字符的原字符串子串。

动态规划,由于可以对子串进行删除操作,我首先想到了LCS问题,但需要枚举所有的长度,这样复杂度为O(N^3),不可取。

由于长度线性增加,考虑使用二分查找目的长度,这样复杂度为O(N^2*log(N))。

需要查找两次,查找子串(ln)的长度等于被查找子串(ln+k)的LCS长度,那么存在相应的子串互补,其中k为删掉的字符数,题中为2。

这样题中复杂度与k无关。但是,这个方法一直没有AC,正确与否需要大牛来指正。