14 algorithm dynamic-programming levenshtein-distance
以下是将字符串转换为具有最少操作数的回文结构的问题状态.我知道它与Levenshtein距离类似 但我还不能解决它
例如,对于输入mohammadsajjadhossain,输出是8.
在弦上执行Levenshtein距离及其反向.解决方案将是从左下角到右上角的DP阵列对角线中的最小操作,以及恰好在对角线上方和正下方的每个条目.
这是有效的,因为沿对角线的条目表示使字符串的第一个和最后一个Ni字符相等所需的最小编辑,正好在上方和下方的条目表示以奇数长度结束的字符串的最小值(中间的) -over)字符与任何东西都不匹配.