首页 > 代码库 > {CSDN}{英雄会}{反相互}
{CSDN}{英雄会}{反相互}
思路:
给定一个字符串,求两个不重叠的字串,他们翻转互补。其中一个字符串可以是删掉最多两个字符的原字符串子串。
动态规划,由于可以对子串进行删除操作,我首先想到了LCS问题,但需要枚举所有的长度,这样复杂度为O(N^3),不可取。
由于长度线性增加,考虑使用二分查找目的长度,这样复杂度为O(N^2*log(N))。
需要查找两次,查找子串(ln)的长度等于被查找子串(ln+k)的LCS长度,那么存在相应的子串互补,其中k为删掉的字符数,题中为2。
这样题中复杂度与k无关。但是,这个方法一直没有AC,正确与否需要大牛来指正。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。