我给出了类似abca的单词。我想知道我需要添加多少个字母才能使其成为回文。在这种情况下是1，因为如果我加b，我得到abcba。
首先，让我们考虑一个低效的递归解决方案：
假设字符串的形式为aSb，其中a和b是字母，S是子字符串。
如果是a==b，则是f(aSb) = f(S)。
如果是a!=b，则需要添加一个字母：要么在末尾添加a，要么在前面添加b。我们需要两者兼而有之，看看哪一个更好。所以在这种情况下，f(aSb) = 1 + min(f(aS), f(Sb))。
这可以用递归函数来实现，该函数需要指数时间才能运行。
为了提高性能，请注意，此函数将仅使用原始字符串的子字符串进行调用。只有O（n^2）个这样的子字符串。因此，通过记忆这个函数的结果，我们以O（n^2）空间为代价，减少了O（n^2）所花费的时间。
基本算法如下所示：
- 遍历字符串的一半，并检查另一端的适当位置是否存在字符（即，如果有
abca，则第一个字符是a，字符串也以a结束）。- 如果匹配，则继续下一个字符
- 如果它们不匹配，请注意需要添加一个字符
请注意，只有当字符匹配时，才能从末尾向后移动单词。例如，如果字符串是abcdeffeda，则外部字符匹配。然后我们需要考虑bcdeffed。外部字符不匹配，因此需要添加一个b。但我们不想继续使用cdeffe（即，删除/忽略两个外部字符），我们只需删除b并继续查看cdeffed。类似地，对于c，这意味着我们的算法返回2字符串修改，而不是更多。