NeetCode #172LC-214HardArrays & Hashing
← Back to All Problems#172 · #214 · Shortest Palindrome(最短回文串)
📌 Problem Statement & Constraints
You are given a string
s. You can convert it to a palindrome by adding characters in front of it. Return the shortest palindrome you can find this way. Constraints: 0 <= s.length <= 5 * 10^4.💡 Core Algorithmic Approaches
- The characters we must prepend are exactly the reverse of the suffix of
sthat is not part of the longest palindromic prefix ofs. - So the task reduces to finding the longest prefix of
sthat is a palindrome. - KMP trick: build the string
t = s + "#" + reverse(s)and compute the KMP failure array. The last entry gives the length of the longest prefix ofsthat is also a suffix ofreverse(s)-- which is exactly the longest palindromic prefix ofs. - Then the answer is
reverse(s)[: len(s) - longest] + s.
💻 Benchmark Python3 Implementation
class Solution:
def shortestPalindrome(self, s: str) -> str:
if not s:
return ""
rev = s[::-1]
# KMP failure array over s + '#' + reverse(s)
t = s + "#" + rev
lps = [0] * len(t)
j = 0
for i in range(1, len(t)):
while j and t[i] != t[j]:
j = lps[j - 1] # fall back
if t[i] == t[j]:
j += 1
lps[i] = j
longest = lps[-1] # longest palindromic prefix of s
return rev[:len(s) - longest] + s⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) with KMP: building the failure array is linear in the length of s + "#" + reverse(s).
💾 Space Complexity
O(n) for the failure array and the reversed string.
⚠️ Interview Pitfalls & Follow-ups
- Using
s + reverse(s)without the'#'separator: the failure array could match across the boundary, producing a prefix longer thanlen(s). - Searching for the longest palindromic prefix by brute force: O(n^2), far too slow at n = 5 * 10^4.
- Reversing the wrong part: the prepended characters are
reverse(s)[: n - longest], i.e. the reverse of the suffix that is not in the palindromic prefix. - Returning
swhen it is already a palindrome:longest == len(s)makes the prepended part empty, which the formula handles correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.