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.
1def shortestPalindrome(s):
2 if s == s[::-1]:
3 return s
4 for i in range(len(s) - 1, -1, -1):
5 if s[:i] == s[:i][::-1]:
6 return s[i:][::-1] + s
7 return ""
8In this Python solution, we start by checking if the entire string s is already a palindrome. If it is, we return it immediately. Otherwise, we iteratively reduce the considered prefix of s and check if it forms a palindrome. Once a palindromic prefix is found, we append the reverse of the unmatched suffix before s.
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.
1function shortestPalindrome(s) {
2 constThis JavaScript solution follows the same methodology as the Java solution using KMP. After forming new_s and computing the LPS array, it determines the longest palindromic prefix. The reversed suffix is prepended to form the shortest palindrome possible.