PythonHaven | Palindrome Check

Problem Statement

The problem being addressed here is to determine whether a given string is a palindrome or not. A palindrome is a string reading the same backward as forward (e.g., "racecar", "level", "radar").

There are various ways to implement this algorithm. I will use various examples from the less optimum to the most optimum to drive the point home.

Implementation: Approach 1

# O(n^2) time | space O(n)
def palindrome_check(string):
	new=""
	for i in reversed(string):
		new +=i 
	if string == new:
		return True
	else:
		return False

print(palindrome_check("abcdcba"))

The function iterates through the characters of the input string in reverse order, constructs a new string by appending each character in reverse order, and then compares the original string with the reversed string to determine if they are equal.

If the two strings are equal, it concludes that the input string is a palindrome; otherwise, it determines that the input string is not a palindrome.

However, this approach is not the most efficient way to check for palindromes, especially for longer strings, because it constructs an entirely new string in memory by appending characters in reverse order.

This can lead to increased memory usage and slower performance, especially for large input strings.

Implementation: Approach 2

# O(n) time | space O(n) - memory usage coz of recursion
def palindrome_check(string):
	new=[]
	for i in reversed(string):
		new.append(i)
	reversed_str ="".join(new)
	if string == reversed_str:
		return True
	else:
		return False

print(palindrome_check("abcdcba"))

Here's a variation of the first solution which improves the time complexity by using a list instead of a string to create the reversed string.

Implementation: Approach 3

# O(n) time | O(n) space -callstack
def palindrome_check(string, i=0):
	j =len(string)-1-i
	
	return True if i>=j else string[i] == string[j] and palindrome_check(string, i+1)

print(palindrome_check("abcdcba"))

This third implementation is very similar to the second approach because they both have the same time & space complexity. However, the thought processes behind the solutions differ.

This function essentially uses a recursive approach to compare characters from both ends of the string towards the middle. It utilizes a base case to handle the termination condition of the recursion when all characters have been compared.

The variable j is calculated as the index of the last character in the string minus i. This gives us the index of the character to be compared with the character at index i.
If i is not greater than or equal to j, the recursive call proceeds by comparing characters at indices i and j and moving towards the middle of the string.

If they are equal, it makes a recursive call with i+1 to move towards the middle of the string. This recursive call checks the next pair of characters.

If any pair of characters is not equal, it immediately returns False, indicating that the string is not a palindrome.

Otherwise, if all characters are successfully compared without finding any inequality, it returns True, indicating that the string is a palindrome.

It uses a single line of code with a ternary expression to handle the recursive comparison. It effectively checks for palindrome properties while minimizing code verbosity.

Implementation: Approach 4 (Tail Recursion)

# O(n) time | O(n) space -callstack
def is_palindrome_tail(string, i=0):
	j =len(string)-1-i
	
	if i>=j:
		return True 
	
	if string[i] != string[j]:
		return False
	
	return is_palindrome_tail(string, i+1)

print("Palindrome Tail recursion: ", is_palindrome_tail("abcdcba"))

This solution uses tail recursion to check for palindrome property. Tail recursion is a special form of recursion where the recursive call is the last operation performed by the function before returning its result. In this solution, the recursive call is the last operation, hence it is tail recursion.

Here's a step-by-step breakdown of the solution and the thought process behind it:

Function Signature

The function is_palindrome_tail takes two parameters: the input string string and an optional parameter i which represents the current index being compared. If i is not provided, it defaults to 0, indicating the start of the string.

Base Cases

The function checks if i has reached the middle of the string or beyond (i >= j). If i is greater than or equal to j, it means that all characters in the string have been compared, and the function returns True, indicating that the string is a palindrome.

This serves as the base case for the recursion.

Comparison

If i is not yet greater than or equal to j, the function compares the characters at indices i and j. If they are not equal, it immediately returns False, indicating that the string is not a palindrome.

Recursive Call

If the characters at indices i and j are equal, the function makes a recursive call with incremented i (i + 1). This moves the comparison towards the middle of the string.

Returning Result

The function returns the result of the recursive call, propagating it back up the call stack until it reaches the initial call.

Output

The function is called with the test string "abcdcba" and prints whether it is a palindrome or not.

The thought process behind using tail recursion in this solution is to efficiently check for the palindrome property by comparing characters from both ends of the string toward the middle.

By incrementing i in each recursive call, the function moves closer to the middle of the string with each comparison, eventually determining whether the entire string is a palindrome or not.

This approach simplifies the logic and avoids unnecessary processing, making it an efficient solution for checking palindrome strings.

Time Complexity Analysis

The function recursively compares characters from both ends of the string towards the middle.

At each step, it performs constant-time operations: character comparison and index increment.

The number of recursive calls is proportional to half the length of the string (because we're comparing characters from both ends towards the middle).

Therefore, the time complexity can be expressed as O(n/2), which simplifies to O(n), where n is the length of the input string.

Space Complexity Analysis

Since the function uses tail recursion, the recursive calls are optimized by the compiler/interpreter, and the space complexity is O(1).

However, if tail call optimization is not available (which is often the case in Python), each recursive call consumes space on the call stack.

In the worst case, where the input string is a palindrome and the recursion goes until reaching the middle of the string, the maximum depth of the call stack is O(n/2), which simplifies to O(n).

Therefore, the space complexity of the function is O(n) due to the recursion stack.

Implementation: Approach 5 (Most Efficient in terms of Complexity)

# O(n) time  | O(1) space
def is_palindrome(string):
	start =0
	end = len(string)-1
	while start < end:
		if string[start] != string[end]:
			return False
		start +=1
		end -=1
	return True
	
print("palindrome::", is_palindrome("abcdcba"))

This function efficiently checks for palindrome property by comparing characters from both ends towards the middle of the string. By using two pointers (start and end) to traverse the string.

It avoids unnecessary comparisons and terminates early if any pair of characters are found to be unequal.

This approach is more efficient than the other approaches, as it only requires iterating through the string once. Additionally, it has a space complexity of O(1) since it doesn't require any additional memory beyond the input string itself.

Overall, this solution provides a simple and effective way to determine whether a given string is a palindrome, with a time complexity of O(n), where n is the length of the input string.

Unit Tests

Here's some unit tests to determine the accuracy and robustness of this solution

import unittest

class TestIsPalindrome(unittest.TestCase):
    def test_palindrome(self):
        # Test case where input is a palindrome
        self.assertTrue(is_palindrome("abcdcba"))

        # Test case where input is an empty string
        self.assertTrue(is_palindrome(""))

        # Test case where input is a single character
        self.assertTrue(is_palindrome("a"))

        # Test case where input is a palindrome with spaces
        self.assertFalse(is_palindrome("A man a plan a canal Panama"))

    def test_not_palindrome(self):
        # Test case where input is not a palindrome
        self.assertFalse(is_palindrome("hello"))

        # Test case where input is a string with numbers
        self.assertTrue(is_palindrome("12321"))

        # Test case where input is a string with special characters
        self.assertFalse(is_palindrome("!@#$%^&*()"))

if __name__ == '__main__':
    unittest.main()

Palindrome Check