💡 Problem Formulation: A common problem in programming and computer science is determining if a string is a palindrome. A palindrome is a word, phrase, number, or other sequences of characters which reads the same backward as forward. This article discusses various methods to check for palindromes in Python by using a stack data structure, through which characters are pushed and popped to verify symmetry. For instance, the input “racecar” should return true as it is a palindrome.
Method 1: Using a List as a Stack
This method uses the list data structure in Python as a stack to push and pop characters. We iterate over the string, pushing characters onto the stack, and then pop them to check against the sequence in the original string.
Here’s an example:
def is_palindrome(string):
stack = []
for char in string:
stack.append(char)
reversed_string = ''
while stack:
reversed_string += stack.pop()
return string == reversed_string
print(is_palindrome("racecar"))Output: True
This code snippet defines a function is_palindrome() that takes a string, iterates over each character to add it to a stack, and then constructs the reversed string by popping characters from the stack. Finally, it checks if the original string is equal to the reversed one to determine if it is a palindrome.
Method 2: Using Collections.deque as a Stack
The collections.deque is a more efficient stack alternative for large datasets. Unlike lists, deques are optimized for quick append and pop operations from both ends.
Here’s an example:
from collections import deque
def is_palindrome(string):
stack = deque()
for char in string:
stack.append(char)
reversed_string = ''.join(stack.pop() for _ in range(len(stack)))
return string == reversed_string
print(is_palindrome("radar"))Output: True
This code snippet uses collections.deque to create a stack with more efficient memory operations for our palindrome check. The stack is then iteratively popped and concatenated into a new string to compare with the original string.
Method 3: Using Half-Stack Optimization
To optimize, we only need to use a stack for the first half of the string. We can compare the remainder of the string with the popped characters from the stack.
Here’s an example:
def is_palindrome(string):
stack = []
length = len(string)
for i in range(length // 2):
stack.append(string[i])
for i in range((length + 1) // 2, length):
if stack.pop() != string[i]:
return False
return True
print(is_palindrome("noon"))Output: True
The function is_palindrome() pushes half of the string onto a stack, then compares the rest of the string with the elements popped from the stack, which optimizes for time and space complexity as compared to the complete traversal.
Method 4: Using a Stack with Pointer Comparison
This method uses a two-pointer technique with a stack. One pointer starts at the beginning of a string, while the other starts at the end, moving towards the center while comparing characters.
Here’s an example:
def is_palindrome(string):
stack = []
start, end = 0, len(string) - 1
while start <= end:
if string[start] != string[end]:
return False
stack.append(string[start])
start += 1
end -= 1
return True
print(is_palindrome("abba"))Output: True
This code avoids the need to construct the entire reversed string by using pointer comparison and a stack. If a mismatch is found during the comparison, the function immediately returns False; otherwise, it continues until the pointers meet in the middle.
Bonus One-Liner Method 5: Using Python’s Extended Slicing
Python’s extended slice syntax offers a concise one-liner that reverses a string and checks for a palindrome without an explicit stack.
Here’s an example:
is_palindrome = lambda string: string == string[::-1]
print(is_palindrome("level"))Output: True
The lambda function is_palindrome uses slicing to reverse the string string[::-1] and compares it to the original string to determine if it’s a palindrome.
Summary/Discussion
- Method 1: Using a List as Stack. Simplest implementation. It may not be the most efficient due to list operations.
- Method 2: Using Collections.deque as a Stack. More memory efficient than Method 1 for larger strings but slightly complex due to import requirements.
- Method 3: Half-Stack Optimization. Saves memory and is faster as it only processes half of the string. The logic is slightly more complex to understand.
- Method 4: Stack with Pointer Comparison. Efficient memory usage and fast performance as it avoids building a reversed string. However, the code is more complex due to pointer management.
- Bonus Method 5: Extended Slicing. Extremely concise and elegant. Doesn’t explicitly use a stack, thus may not fulfill stack utilization requirements in some cases.