Description
You are given a string 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.
Examples:
Example 1:
Input: s = "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: s = "abcd"
Output: "dcbabcd"Solution in Python
To solve the problem of finding the shortest palindrome by adding characters in front of a given string s, we can utilize the concept of finding the longest prefix of s that is also a suffix of its reverse. This can be done using the KMP (Knuth-Morris-Pratt) algorithm’s approach to compute the “Longest Prefix which is also Suffix” (LPS) array.
Steps to Solve the Problem:
- Reverse the String: Let’s call the reversed string
rev_s. - Combine Strings: Create a new string by concatenating
s + '#' + rev_s. The#is a special character that ensures there is no overlap betweensandrev_s. - Compute LPS Array: The LPS array is calculated for the combined string. The value of the last element of the LPS array will tell us the length of the longest palindrome prefix in the original string
s. - Construct the Result: Add the necessary characters (which are the characters in
sthat are not part of the longest palindrome prefix) in reverse order to the front of the original strings.
Python
class Solution:
def shortestPalindrome(self, s: str) -> str:
# Reverse the string s
rev_s = s[::-1]
# Create a new string combining s, a separator '#', and rev_s
new_s = s + '#' + rev_s
# Compute the LPS (Longest Prefix Suffix) array for new_s
lps = self.computeLPSArray(new_s)
# Find the length of the longest palindrome prefix
longest_palindrome_prefix_len = lps[-1]
# Characters that need to be added to the front to make the string a palindrome
to_add = rev_s[:len(s) - longest_palindrome_prefix_len]
# Return the shortest palindrome by adding the necessary characters in front
return to_add + s
def computeLPSArray(self, s: str) -> list:
n = len(s)
lps = [0] * n
length = 0 # length of the previous longest prefix suffix
i = 1
# Loop through the string to calculate LPS values
while i < n:
if s[i] == s[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
# Consider the previous longest prefix suffix
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lpsExplanation:
- Reversing the String:
rev_s = s[::-1]reverses the strings.
- Combining Strings:
new_s = s + '#' + rev_screates a new string that is the concatenation ofs, a separator#, andrev_s.
- Computing the LPS Array:
computeLPSArray(new_s)generates the LPS array fornew_s.- The LPS array helps us find the longest prefix of
sthat is also a suffix in the combined string. This indicates the largest palindromic prefix.
- Constructing the Result:
to_add = rev_s[:len(s) - longest_palindrome_prefix_len]calculates the characters fromrev_sthat need to be added in front ofsto form a palindrome.- The final result is the concatenation of
to_addand the original strings.
Final Result:
The function returns the shortest palindrome that can be formed by adding the minimum number of characters in front of the original string s. This approach is efficient, leveraging the properties of string patterns and the KMP algorithm.
Solution in Javascript
JavaScript
var shortestPalindrome = function(s) {
// Reverse the string s
const rev_s = s.split('').reverse().join('');
// Create a new string combining s, a separator '#', and rev_s
const new_s = s + '#' + rev_s;
// Compute the LPS (Longest Prefix Suffix) array for new_s
const lps = computeLPSArray(new_s);
// Find the length of the longest palindrome prefix
const longest_palindrome_prefix_len = lps[lps.length - 1];
// Characters that need to be added to the front to make the string a palindrome
const to_add = rev_s.slice(0, s.length - longest_palindrome_prefix_len);
// Return the shortest palindrome by adding the necessary characters in front
return to_add + s;
};
// Helper function to compute the LPS array
function computeLPSArray(s) {
const n = s.length;
const lps = new Array(n).fill(0);
let length = 0; // Length of the previous longest prefix suffix
let i = 1;
// Loop through the string to calculate LPS values
while (i < n) {
if (s[i] === s[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length !== 0) {
// Consider the previous longest prefix suffix
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}Solution in Java
Java
class Solution {
public String shortestPalindrome(String s) {
// Reverse the string s
String rev_s = new StringBuilder(s).reverse().toString();
// Create a new string combining s, a separator '#', and rev_s
String new_s = s + "#" + rev_s;
// Compute the LPS (Longest Prefix Suffix) array for new_s
int[] lps = computeLPSArray(new_s);
// Find the length of the longest palindrome prefix
int longestPalindromePrefixLen = lps[lps.length - 1];
// Characters that need to be added to the front to make the string a palindrome
String toAdd = rev_s.substring(0, s.length() - longestPalindromePrefixLen);
// Return the shortest palindrome by adding the necessary characters in front
return toAdd + s;
}
// Helper method to compute the LPS array
private int[] computeLPSArray(String s) {
int n = s.length();
int[] lps = new int[n];
int length = 0; // length of the previous longest prefix suffix
int i = 1;
// Loop through the string to calculate LPS values
while (i < n) {
if (s.charAt(i) == s.charAt(length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
// Consider the previous longest prefix suffix
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
}Solution in C#
C#
public class Solution {
public string ShortestPalindrome(string s) {
// Reverse the string s
string rev_s = ReverseString(s);
// Create a new string combining s, a separator '#', and rev_s
string new_s = s + "#" + rev_s;
// Compute the LPS (Longest Prefix Suffix) array for new_s
int[] lps = ComputeLPSArray(new_s);
// Find the length of the longest palindrome prefix
int longestPalindromePrefixLen = lps[lps.Length - 1];
// Characters that need to be added to the front to make the string a palindrome
string toAdd = rev_s.Substring(0, s.Length - longestPalindromePrefixLen);
// Return the shortest palindrome by adding the necessary characters in front
return toAdd + s;
}
// Helper method to reverse a string
private string ReverseString(string s) {
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
// Helper method to compute the LPS array
private int[] ComputeLPSArray(string s) {
int n = s.Length;
int[] lps = new int[n];
int length = 0; // length of the previous longest prefix suffix
int i = 1;
// Loop through the string to calculate LPS values
while (i < n) {
if (s[i] == s[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
// Consider the previous longest prefix suffix
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
}