algorithm - 如何以最少的操作将字符串转换为回文？

Question

这是 problem状态以最少的操作次数将字符串转换为回文。我知道它类似于 Levenshtein distance 但我还不能解决它

例如，对于输入mohammadsajjadhossain，输出是8。

Answer 1

对字符串及其反向执行 Levenshtein 距离。解决方案将是 DP 数组对角线上从左下角到右上角的操作的最小值，以及对角线上方和下方的每个条目。

这是可行的，因为沿对角线的条目表示使字符串的第一个 i 和最后 N-i 个字符相等所需的最少编辑，而正上方和正下方的条目代表以奇数长度结尾的字符串的最小值，其中中间(左侧)字符与任何内容都不匹配。