如何以最少的操作次数将字符串转换为回文？
这是 问题 表示以最少的操作次数将字符串转换为回文。我知道它类似于 Levenshtein 距离 但我还无法解决它
例如，对于输入mohammadsajjadhossain，输出是8。
Here is the problem states to convert a string into a palindrome with minimum number of operations. I know it is similar to the Levenshtein distance
but I can't solve it yet
For example, for input mohammadsajjadhossain, the output is 8.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对字符串及其反面执行 Levenshtein 距离。解决方案将是 DP 数组的对角线中从左下角到右上角的操作的最小值，以及对角线上方和下方的每个条目。
这是有效的，因为沿对角线的条目表示使字符串的前 i 和最后 Ni 字符相等所需的最小编辑量，而上方和下方的条目表示以奇数长度结尾的字符串的最小值，其中中间（左） -over) 字符与任何内容都不匹配。
Perform Levenshtein distance on the string and its reverse. The solution will be the minimum of the operations in the diagonal of the DP array going from bottom-left to top-right, as well as each entry just above and just below the diagonal.
This works because the entries along the diagonal represent the minimum edits required to make the first i and last N-i characters of the string equal and the entries just above and just below represent the minimum for strings ending up with odd-length where the middle (left-over) character doesn't match against anything.
您只需要计算有限数量的编辑距离，每个可能的回文枢轴点一个。枢轴点可以是一个字母，也可以位于两个字母之间，因此长度为 n 的字符串有 2n-1 个枢轴点。对于每个枢轴点，您计算枢轴点之前的字符及其之后的字符的反向编辑距离：
(m)ohammadsajjadhossain: Levensthein("", "niassohdajjasdammaho")m ohammadsajjadhossain：Levensthein("m", "niassohdajjasdammaho")m(o)hammadsajjadhossain: Levensthein("m", "niassohdajjasdammah")mo hammadsajjadhossain：Levensthein("mo", "niassohdajjasdammah")mo(h)ammadsajjadhossain: Levensthein("mo", "niassohdajjasdamma")moh ammadsajjadhossain：Levensthein("moh", "niassohdajjasdamma")等等。
现在只需取这些距离中的最小值即可。如果速度很重要，您可以优化掉许多此类调用。
You just need to compute a limited number of Levenshtein distances, one for each possible palindrome pivot point. A pivot point can be a letter or it can be between two letters, so a string of length n has 2n-1 pivot points. For each pivot point, you calculate the Levenshtein distance of the characters before the pivot point and the reverse of the characters after it:
(m)ohammadsajjadhossain: Levensthein("", "niassohdajjasdammaho")m ohammadsajjadhossain: Levensthein("m", "niassohdajjasdammaho")m(o)hammadsajjadhossain: Levensthein("m", "niassohdajjasdammah")mo hammadsajjadhossain: Levensthein("mo", "niassohdajjasdammah")mo(h)ammadsajjadhossain: Levensthein("mo", "niassohdajjasdamma")moh ammadsajjadhossain: Levensthein("moh", "niassohdajjasdamma")etc.
Now just take the minimum of these distances. If speed is important, you can optimise away many of these calls.