Closed mah-shamim closed 3 hours ago
We need to find the shortest palindrome by adding characters in front of a given string. We can approach this by identifying the longest prefix of the string that is already a palindrome. Once we have that, the remaining part can be reversed and added to the front to make the entire string a palindrome.
s
that is already a palindrome.To do this efficiently, we can use string matching techniques such as the KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix.
Create a new string by appending the reverse of the string s
to s
itself, separated by a special character '#'
to avoid overlap between the string and its reverse.
Let the new string be s + '#' + reverse(s)
.
Use the KMP partial match table (also known as the LPS array, longest prefix suffix) on this new string to determine the longest prefix of s
that is also a suffix. This will give us the length of the longest palindromic prefix in s
.
Construct the shortest palindrome by adding the necessary characters to the front.
Let's implement this solution in PHP: 214. Shortest Palindrome
<?php
/**
* @param String $s
* @return String
*/
function shortestPalindrome($s) {
// If the string is empty, return an empty string
if (empty($s)) {
return $s;
}
// Reverse of the string
$rev_s = strrev($s);
// Form the new string as s + '#' + reverse(s)
$combined = $s . '#' . $rev_s;
// Compute the LPS array for this combined string
$lps = computeLPS($combined);
// Length of the longest palindromic prefix in s
$longest_palindromic_prefix_len = $lps[strlen($combined) - 1];
// The characters that need to be added to the front are the remaining part of the string
$remaining = substr($s, $longest_palindromic_prefix_len);
// Add the reverse of the remaining part to the front of s
return strrev($remaining) . $s;
}
/**
* Helper function to compute the KMP (LPS array) for string matching
*
* @param $pattern
* @return array
*/
function computeLPS($pattern) {
$n = strlen($pattern);
$lps = array_fill(0, $n, 0);
$len = 0;
$i = 1;
while ($i < $n) {
if ($pattern[$i] == $pattern[$len]) {
$len++;
$lps[$i] = $len;
$i++;
} else {
if ($len != 0) {
$len = $lps[$len - 1];
} else {
$lps[$i] = 0;
$i++;
}
}
}
return $lps;
}
?>
computeLPS Function:
s
is already a palindrome.Forming the Combined String:
s
with its reverse and separate them by a special character #
. The special character ensures that there is no overlap between s
and reverse(s)
.Using the LPS Array:
s
which is also a suffix of s
. This corresponds to the longest part of the string that is already a palindrome.Constructing the Shortest Palindrome:
s
.n
is the length of the string. This is because we are using the KMP algorithm, which runs in linear time.Input: s = "aacecaaa"
s
: "aaacecaa"
"aacecaaa#aaacecaa"
"aacecaaa"
.Since the whole string is already a palindrome, no characters need to be added. So the output is "aaacecaaa"
.
Input: s = "abcd"
s
: "dcba"
"abcd#dcba"
"a"
.So, we add "dcb"
(reverse of "bcd"
) to the front of s
, resulting in "dcbabcd"
.
This solution efficiently finds the shortest palindrome by leveraging string matching techniques and the KMP algorithm to identify the longest palindromic prefix. The complexity is linear, making it suitable for large input sizes up to 5 * 10^4
.
Discussed in https://github.com/mah-shamim/leet-code-in-php/discussions/577
0 <= s.length <= 5 * 104
- `s` consists of lowercase English letters only. [^1]: **Palindrome** `A **palindrome** is a string that reads the same forward and backward.`