How to Find the Shortest Palindrome by Adding Characters in Python
Creating the shortest palindrome by appending characters to a given string is a common algorithmic problem. This can be approached efficiently using a combination of string manipulation and pattern matching techniques. Below is a Python function that implements this logic.
Function Definition
The function shortest_palindrome calculates the shortest palindrome that can be generated by adding characters to the beginning of the input string. It utilizes the KMP (Knuth-Morris-Pratt) algorithm to ascertain how much of the original string's prefix can match with its reversed suffix.
Code Implementation
def shortest_palindrome(s: str) -> str:
if not s:
return ""
# Create a new string that is the original string + a unique separator + its reverse
new_string = s + "#" + s[::-1]
n = len(new_string)
# KMP table (Prefix function)
kmp = [0] * n
# Build the KMP table
for i in range(1, n):
j = kmp[i - 1]
while j > 0 and new_string[i] != new_string[j]:
j = kmp[j - 1]
if new_string[i] == new_string[j]:
j += 1
kmp[i] = j
# The length of the longest palindromic prefix
longest_palindromic_prefix_len = kmp[-1]
# Calculate how many characters to add
chars_to_add = s[longest_palindromic_prefix_len:][::-1]
# Form the shortest palindrome
return chars_to_add + s
# Example Usage
input_string = "race"
result = shortest_palindrome(input_string)
print(f"The shortest palindrome that can be formed is: '{result}'")
Explanation of the Code
1. Edge Case Handling: If the input string is empty, the function returns an empty string immediately.
2. String Preparation: We create a new string consisting of the original string followed by a unique separator ('#') and the reverse of the original string. This helps in applying the KMP algorithm to find the longest palindromic prefix.
3. KMP Table Construction: The KMP table is computed to identify the longest prefix of the new string which also serves as a suffix. This effectively indicates the length of the longest palindromic prefix in the original string.
4. Calculating Characters to Add: By examining the characters in the original string that are not part of the longest palindromic prefix, we can reverse this segment and prepend it to the original string to form the shortest palindrome.
5. Final Result: The shortest palindrome is formed by combining the reversed characters necessary for completion with the original string.
Complexity Analysis
- Time Complexity: The algorithm runs in \(O(n)\) where \(n\) is the length of the original string due to the linear scan for KMP.
- Space Complexity: The space complexity is also \(O(n)\) due to the storage of the KMP table.
This approach ensures efficiency and clarity, resulting in a robust solution for creating the shortest palindrome from an input string.