IVl*_*lad 18 algorithm math recurrence dynamic-programming
我最近发现了一个竞赛问题,要求您计算字符串中必须插入的最小字符数(任何地方)以将其转换为回文结构.
例如,给定字符串:"abcbd"我们可以通过插入两个字符将其转换为回文:一个在"a"之后,另一个在"d"之后:"a d bcbd a ".
这似乎是一个类似问题的概括,要求同样的事情,除了字符只能在最后添加 - 这在使用哈希表的O(N)中有一个非常简单的解决方案.
我一直试图修改Levenshtein距离算法来解决这个问题,但还没有成功.任何有关如何解决这个问题的帮助(它不一定非常有效,我只对任何DP解决方案感兴趣)将不胜感激.
小智 7
注意:这只是一种好奇心.Dav提出了一种算法,该算法可以修改为DP算法,以便在O(n ^ 2)时间和O(n ^ 2)空间中容易地运行(并且可能具有更好的簿记O(n)).
当然,如果您决定更改允许的操作,这种"天真"算法实际上可能会派上用场.
这是一个'天真'的算法,可以通过聪明的簿记更快地完成.
给定一个字符串,我们猜测得到的回文的中间位置然后尝试计算使字符串成为该中间周围的回文所需的插入次数.
如果字符串的长度为n,则有2n + 1个可能的middles(每个字符,在两个字符之间,就在字符串之前和之后).
假设我们考虑一个中间部分,它给出了两个字符串L和R(一个到左边,一个到右边).
如果我们使用插入,我相信最长公共子序列算法(这是一个DP算法)现在可以用来创建一个包含L和R的反向的"超级"字符串,参见Shortest common supersequence.
选择中间部分,为您提供最小数量的插入.
我相信这是O(n ^ 3).(注意:我没有尝试证明这是真的).