Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 214 with 16 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 214 # by problem number
lcpy gen -s shortest_palindrome # by problem name
s. You can convert s to a palindrome by adding characters in front of it.
Return the shortest palindrome you can find by performing this transformation.
Input: s = "aacecaaa"
Output: "aaacecaaa"
Input: s = "abcd"
Output: "dcbabcd"
class Solution:
# Time: O(n)
# Space: O(n)
def shortest_palindrome(self, s: str) -> str:
if not s:
return s
rev = s[::-1]
combined = s + "#" + rev
n = len(combined)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and combined[i] != combined[j]:
j = pi[j - 1]
if combined[i] == combined[j]:
j += 1
pi[i] = j
longest = pi[-1]
return rev[: len(s) - longest] + s
| Time | Space |
|---|---|
| O(n) | O(n) |