0214. Shortest Palindrome
=========================
题目信息
--------
:题号: 0214. 最短回文串
:难度: Hard
:主题: 字符串、回文前缀、前缀函数、KMP
:原题: `LeetCode 0214 `_
:重点: 只能在开头添加、最长回文前缀、border 复用、失配跳转
题目重述
--------
给定字符串 ``s``,只能在它的开头添加字符,返回得到的最短回文串。原字符串内部的字符顺序不能改变,新增字符不能插入到中间
或末尾;若原串已经是回文,则不需要添加任何字符。输入只含小写英文字母,长度最多为 ``5 * 10^4``。
自建示例
--------
``s = "abcd"`` 返回 ``"dcbabcd"``。原串中能保留的最长回文前缀只有 ``"a"``,未保留后缀 ``"bcd"`` 的逆序 ``"dcb"``
必须放到前面;保留 ``"ab"`` 不能修复 ``ab`` 内部已经存在的非回文关系。
``s = "aacecaaa"`` 的最长回文前缀是 ``"aacecaa"``,只需在前面添加剩余字符 ``"a"`` 的逆序,结果仍是原串本身。
``s = "aba"`` 已经是回文,答案为 ``"aba"``;``s = ""`` 返回空串。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
static bool isPalindrome(const std::string& text, int right) {
int left = 0;
while (left < right) {
if (text[left++] != text[right--]) return false;
}
return true;
}
static std::string byCheckingPrefixes(const std::string& s) {
for (int prefix = static_cast(s.size()); prefix >= 0; --prefix) {
if (prefix > 0 && !isPalindrome(s, prefix - 1)) continue;
std::string reversed = s.substr(prefix);
std::reverse(reversed.begin(), reversed.end());
return reversed + s;
}
return s;
}
static std::string byPrefixFunction(const std::string& s) {
if (s.empty()) return s;
std::string reversed = s;
std::reverse(reversed.begin(), reversed.end());
const std::string combined = s + '#' + reversed;
std::vector lps(combined.size(), 0);
for (std::size_t i = 1; i < combined.size(); ++i) {
int length = lps[i - 1];
while (length > 0 && combined[i] != combined[length]) {
length = lps[length - 1];
}
if (combined[i] == combined[length]) ++length;
lps[i] = length;
}
const int palindrome_prefix = lps.back();
std::string answer = reversed.substr(0, s.size() - palindrome_prefix);
answer += s;
return answer;
}
public:
std::string shortestPalindrome(const std::string& s) {
return byPrefixFunction(s);
}
};
题解
----
先确定能保留的原串
~~~~~~~~~~~~~~~~~~~~
新增字符只能放在开头。若保留原串前缀 ``s[0..p)``,剩余后缀 ``s[p..n)`` 的镜像只能放到最前面,构造被唯一确定为:
.. code-block:: text
reverse(s[p..n)) + s
它成为回文的必要条件是保留的前缀本身是回文;同时 ``p`` 越大,新增字符越少。因此题目不是在所有新字符串中搜索,
而是在所有前缀中寻找最长回文前缀。
前缀枚举基线
~~~~~~~~~~~~
从 ``p=n`` 向下尝试,每次从两端检查 ``s[0..p)`` 是否回文,第一次成功就能构造最短答案。这个方案直接对应定义,
但相邻候选前缀共享绝大部分字符,最坏时间达到 ``O(n^2)``。滚动哈希可以加速单次判断,却需要接受碰撞概率或维护多组哈希,
仍没有解释不同候选之间如何复用失配位置。
把回文前缀变成最长 border
~~~~~~~~~~~~~~~~~~~~~~~~~~
令 ``r = reverse(s)``,构造 ``combined = s + '#' + r``,其中 ``#`` 不在小写字母输入域中。若 ``s`` 的前缀长度为 ``p`` 且是回文,
它会与 ``r`` 的后缀相同,于是 ``combined`` 存在长度为 ``p`` 的相等前缀和后缀。反过来,分隔符阻止匹配跨越两部分,
所以 ``combined`` 的最长 border(同时是前缀和后缀的字符串)恰好对应最长回文前缀。
前缀函数压缩失配工作
~~~~~~~~~~~~~~~~~~~~~~
``lps[i]`` 表示 ``combined[0..i]`` 的最长 border 长度。处理新字符时先继承 ``lps[i-1]``:相等就延长;失配就跳到
``lps[length-1]`` 代表的更短 border,继续尝试;所有候选都失败才归零。更短 border 本来就是更长 border 的后缀,因此这个跳转
不会漏掉可能接上当前字符的候选。每次跳转都丢弃一批已证明不可能的前缀,整个计算降为线性。
状态走读
~~~~~~~~
对 ``s="abcd"``,组合串为 ``"abcd#dcba"``:
.. list-table::
:header-rows: 1
* - 扫描到
- ``lps`` 的关键状态
- 含义
* - ``a``、``ab``、``abc``、``abcd``
- 末尾都没有相等的真前后缀
- 当前候选长度保持 0
* - ``#``
- 分隔符不能与小写字母匹配
- 跨界候选被切断
* - ``dcb``
- 仍不能接到首字符 ``a``
- 长度保持 0
* - 最后的 ``a``
- 与组合串首字符相等
- ``lps.back() = 1``
因此保留 ``a``,新增 ``dcb``。对于 ``aacecaaa``,边界会沿已知 border 逐步回退和延伸,最后得到长度 7 的回文前缀,
不需要逐个重新检查长度 7、6、5 等候选。得到 ``palindrome_prefix`` 后,代码从 ``reversed`` 取出未保留部分并接回 ``s``。
代码演进与方案选择
~~~~~~~~~~~~~~~~~~~~
``byCheckingPrefixes`` 保留了直接定义,最坏时间为 ``O(n^2)``,其中内层回文检查重复读取前缀。``byPrefixFunction``
把所有候选 border 的关系存入 ``lps``,失配时跳到已知的更短 border,时间降为 ``O(n)``;公共入口选择它,因为不依赖哈希随机性。
``length`` 失配后不能直接归零,较短 border 仍可能接上当前字符;而分隔符必须不在输入字符域,否则可能得到跨界伪匹配。
复杂度与边界
~~~~~~~~~~~~
``byCheckingPrefixes`` 最坏时间为 ``O(n^2)``,``byPrefixFunction`` 时间为 ``O(n)``。主解的反转串、组合串和 ``lps``
共同占用 ``O(n)`` 额外空间;空串和单字符在同一逻辑下自然返回自身,整串回文时新增部分长度为 0。