algorithm - 从给定的单词制作回文

Question

我给出了像 abca 这样的词。我想知道我需要添加多少个字母才能使其成为回文。在本例中为 1，因为如果我添加 b，我将得到 abcba。

Answer 1

首先，让我们考虑一个低效的递归解决方案:

假设字符串的形式是aSb，其中a和b是字母，S是a子串。

如果 a==b，则 f(aSb) = f(S)。

如果a!=b，那么你需要加一个字母:要么在末尾加一个a，要么加一个b在前面。我们需要尝试两者，看看哪个更好。所以在这种情况下，f(aSb) = 1 + min(f(aS), f(Sb))。

这可以通过递归函数来实现，该函数需要指数级的时间来运行。

为了提高性能，请注意该函数将仅使用原始字符串的子字符串进行调用。只有 O(n^2) 个这样的子串。所以通过 memoizing这个函数的结果，我们将花费的时间减少到 O(n^2)，代价是 O(n^2) 空间。