Sponsored
Sponsored
The brute force approach involves checking each prefix of the string to determine if it forms a palindrome. We progressively add characters from the end of the string to the beginning until a valid palindrome is formed.
Time Complexity: O(n^2), where n is the length of the string, due to the repeated palindrome checks.
Space Complexity: O(n) for storing the reversed string.
1#include <string>
2
3std::string shortestPalindrome(std::string s) {
4 std::string rev_s = std::string(s.rbegin(), s.rend());
5 for (int i = s.size(); i >= 0; i--) {
6 if (s.substr(0, i) == rev_s.substr(s.size() - i)) {
7 return rev_s.substr(0, s.size() - i) + s;
8 }
9 }
10 return "";
11}
12This C++ solution uses a similar logic to Python, with minor syntax adjustments. It reverses the string using iterators and checks for palindromic prefixes. For each valid prefix, the solution constructs the shortest palindrome.
This approach uses the KMP (Knuth-Morris-Pratt) algorithm's partial match table (LPS array) to efficiently find the largest palindromic prefix. We concatenate the string with its reverse and compute the LPS array for substring match optimization.
Time Complexity: O(n), where n is the length of the string, due to linear time computation of the LPS array.
Space Complexity: O(n) for the LPS array and interim reversed string.
1public class Solution {
2 public String
In this Java solution, the string is concatenated with a separator and its reverse to form temp. The LPS array is used to find the longest prefix which is also a palindrome. We then reverse the remaining suffix of the original string and prepend it to s to produce the shortest palindrome.