Leetcode Problem 214. Shortest Palindrome

214. Shortest Palindrome

Leetcode Solutions

Approach # KMP (Knuth–Morris–Pratt)

  1. Reverse the original string s to get rev_s.
  2. Concatenate s, #, and rev_s to form new_s.
  3. Initialize an array f with the same length as new_s to store the failure function.
  4. Iterate through new_s to build the failure function f.
  5. Use the last value in f to determine the length of the longest palindromic prefix.
  6. Append the reverse of the remaining suffix to the front of s to form the shortest palindrome.
UML Thumbnail

Approach # Brute Force

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...