Skip to content

Instantly share code, notes, and snippets.

@makoru-hikage
Last active June 30, 2021 13:22
Show Gist options
  • Save makoru-hikage/6460d9e02aa24725af3f47411932c160 to your computer and use it in GitHub Desktop.
Save makoru-hikage/6460d9e02aa24725af3f47411932c160 to your computer and use it in GitHub Desktop.
An O(log_n) palindrome check algorithm, the number of letter iterations is halved (rounded up when the half is a rational number).
#!/bin/bash/python
#
# Requires Python 3 and above
#
# Example
#
# R A D A R
# 1 2 3 4 5
#
# H A N N A H
# 1 2 3 4 5 6
#
# The opposite of 2 is 4... so on, so forth.
def check_palindrome(the_word):
word_length = len(the_word)
# No need to go all the way through...
for i in range(int(word_length / 2)):
# If you have 5 fingers, the third one is the middle
# If the no. of your finger is 6, consider the gap as 3.5
middle_index = (word_length + 1) / 2.00
# Most arrays start at 0, but...
# Letter index must start by 1
li = i + 1
# The opposite version of your 2nd finger is your 4th finger
c = int((middle_index * 2) - li)
#If the opposites don't match...
if the_word[i] != the_word[c - 1]:
return False
return True
print("Enter a word (case sensitive): ")
THE_WORD = input()
print (check_palindrome(THE_WORD))
@makoru-hikage
Copy link
Author

I didn't know how to use the ceiling function back then.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment