LeetCode 214: Shortest Palindrome (KMP Prefix-Suffix on s + '#' + reverse(s))
LeetCode 214StringKMPPrefix FunctionToday we solve LeetCode 214 - Shortest Palindrome.
Source: https://leetcode.com/problems/shortest-palindrome/
English
Problem Summary
Given a string s, you may add characters only in front of it. Return the shortest palindrome you can build.
Key Insight
We need the longest palindromic prefix of s. If its length is L, then the suffix s[L:] is the unmatched tail; reverse that tail and prepend it.
Use KMP prefix function on: t = s + '#' + reverse(s). The final prefix value gives exactly L.
Brute Force and Limitations
Trying all prefixes and checking palindrome each time costs O(n^2), too slow for long strings.
Optimal Algorithm Steps
1) Build r = reverse(s) and t = s + '#' + r.
2) Compute KMP LPS array on t.
3) Let L = lps[t.length-1] (longest palindromic prefix length).
4) Take suffix = s.substring(L), reverse it, prepend to s.
Complexity Analysis
Time: O(n).
Space: O(n).
Common Pitfalls
- Missing delimiter #, causing false overlap across boundaries.
- Using longest palindromic substring instead of palindromic prefix.
- Appending at tail (not allowed); only prepend is valid.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String shortestPalindrome(String s) {
String r = new StringBuilder(s).reverse().toString();
String t = s + "#" + r;
int[] lps = new int[t.length()];
for (int i = 1; i < t.length(); i++) {
int j = lps[i - 1];
while (j > 0 && t.charAt(i) != t.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == t.charAt(j)) j++;
lps[i] = j;
}
int L = lps[t.length() - 1];
String suffix = s.substring(L);
return new StringBuilder(suffix).reverse().toString() + s;
}
}func shortestPalindrome(s string) string {
r := reverseString(s)
t := s + "#" + r
lps := make([]int, len(t))
for i := 1; i < len(t); i++ {
j := lps[i-1]
for j > 0 && t[i] != t[j] {
j = lps[j-1]
}
if t[i] == t[j] {
j++
}
lps[i] = j
}
L := lps[len(t)-1]
suffix := s[L:]
return reverseString(suffix) + s
}
func reverseString(x string) string {
b := []byte(x)
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return string(b)
}class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> lps(t.size(), 0);
for (int i = 1; i < (int)t.size(); ++i) {
int j = lps[i - 1];
while (j > 0 && t[i] != t[j]) j = lps[j - 1];
if (t[i] == t[j]) ++j;
lps[i] = j;
}
int L = lps.back();
string suffix = s.substr(L);
reverse(suffix.begin(), suffix.end());
return suffix + s;
}
};class Solution:
def shortestPalindrome(self, s: str) -> str:
r = s[::-1]
t = s + "#" + r
lps = [0] * len(t)
for i in range(1, len(t)):
j = lps[i - 1]
while j > 0 and t[i] != t[j]:
j = lps[j - 1]
if t[i] == t[j]:
j += 1
lps[i] = j
L = lps[-1]
suffix = s[L:]
return suffix[::-1] + svar shortestPalindrome = function(s) {
const r = s.split('').reverse().join('');
const t = s + '#' + r;
const lps = new Array(t.length).fill(0);
for (let i = 1; i < t.length; i++) {
let j = lps[i - 1];
while (j > 0 && t[i] !== t[j]) j = lps[j - 1];
if (t[i] === t[j]) j++;
lps[i] = j;
}
const L = lps[t.length - 1];
const suffix = s.slice(L);
return suffix.split('').reverse().join('') + s;
};中文
题目概述
给定字符串 s，你只能在字符串前面添加字符。返回可以构造出的最短回文串。
核心思路
关键是找到 s 的最长回文前缀，长度记为 L。那么 s[L:] 这段后缀是未匹配部分，把它反转后前置即可。
用 KMP 前缀函数处理 t = s + '#' + reverse(s)，最后一个 LPS 值就是这个 L。
暴力解法与不足
如果枚举每个前缀再判断是否回文，复杂度会到 O(n^2)，字符串长时会慢。
最优算法步骤
1）构造 r = reverse(s) 与 t = s + '#' + r。
2）对 t 计算 KMP 的 LPS 数组。
3）令 L = lps[t.length-1]。
4）取 suffix = s.substring(L)，反转后拼到前面。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 忘记使用分隔符 #，导致前后串错误串联匹配。
- 误求“最长回文子串”而不是“最长回文前缀”。
- 把字符加到末尾（题目只允许前置）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String shortestPalindrome(String s) {
String r = new StringBuilder(s).reverse().toString();
String t = s + "#" + r;
int[] lps = new int[t.length()];
for (int i = 1; i < t.length(); i++) {
int j = lps[i - 1];
while (j > 0 && t.charAt(i) != t.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == t.charAt(j)) j++;
lps[i] = j;
}
int L = lps[t.length() - 1];
String suffix = s.substring(L);
return new StringBuilder(suffix).reverse().toString() + s;
}
}func shortestPalindrome(s string) string {
r := reverseString(s)
t := s + "#" + r
lps := make([]int, len(t))
for i := 1; i < len(t); i++ {
j := lps[i-1]
for j > 0 && t[i] != t[j] {
j = lps[j-1]
}
if t[i] == t[j] {
j++
}
lps[i] = j
}
L := lps[len(t)-1]
suffix := s[L:]
return reverseString(suffix) + s
}
func reverseString(x string) string {
b := []byte(x)
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return string(b)
}class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> lps(t.size(), 0);
for (int i = 1; i < (int)t.size(); ++i) {
int j = lps[i - 1];
while (j > 0 && t[i] != t[j]) j = lps[j - 1];
if (t[i] == t[j]) ++j;
lps[i] = j;
}
int L = lps.back();
string suffix = s.substr(L);
reverse(suffix.begin(), suffix.end());
return suffix + s;
}
};class Solution:
def shortestPalindrome(self, s: str) -> str:
r = s[::-1]
t = s + "#" + r
lps = [0] * len(t)
for i in range(1, len(t)):
j = lps[i - 1]
while j > 0 and t[i] != t[j]:
j = lps[j - 1]
if t[i] == t[j]:
j += 1
lps[i] = j
L = lps[-1]
suffix = s[L:]
return suffix[::-1] + svar shortestPalindrome = function(s) {
const r = s.split('').reverse().join('');
const t = s + '#' + r;
const lps = new Array(t.length).fill(0);
for (let i = 1; i < t.length; i++) {
let j = lps[i - 1];
while (j > 0 && t[i] !== t[j]) j = lps[j - 1];
if (t[i] === t[j]) j++;
lps[i] = j;
}
const L = lps[t.length - 1];
const suffix = s.slice(L);
return suffix.split('').reverse().join('') + s;
};
Comments