is palindrome Algorithm
There are also numeral palindromes, including date / time stamps use short digits 11/11/11 11:11 and long digits 02/02/2020.Composing literature in palindromes is an example of constrained writing. Byzantine Greeks often inscribed the palindrome," wash [ thy ] sins, not only [ thy ] face" ΝΙΨΟΝ ΑΝΟΜΗΜΑΤΑ ΜΗ ΜΟΝΑΝ ΟΨΙΝ (" Nipson anomēmata mē monan opsin", engraving" ps" with the individual Greek letter Ψ, psi), on baptismal fonts; most notably in the basilica of Hagia Sophia, i.e. of the Holy Wisdom of deity, in Constantinople.
This practice was continued in many churches in Western Europe, such as the font at St. Mary's Church, Nottingham and also the font of St. Stephen d'Egres, Paris; at St. Menin's Abbey, Orléans; at Dulwich College; and at the following churches in England: Worlingworth (Suffolk), Harlow (Essex), Knapton (Norfolk), St Martin, Ludgate (London), and Hadleigh (Suffolk).Palindromes date back at least to 79 ad, as a palindrome was found as a graffito at Herculaneum, a city bury by ash in that year.
def is_palindrome(head):
if not head:
return True
# split the list to two parts
fast, slow = head.next, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
second = slow.next
slow.next = None # Don't forget here! But forget still works!
# reverse the second part
node = None
while second:
nxt = second.next
second.next = node
node = second
second = nxt
# compare two parts
# second part has the same or one less node
while node:
if node.val != head.val:
return False
node = node.next
head = head.next
return True
def is_palindrome_stack(head):
if not head or not head.next:
return True
# 1. Get the midpoint (slow)
slow = fast = cur = head
while fast and fast.next:
fast, slow = fast.next.next, slow.next
# 2. Push the second half into the stack
stack = [slow.val]
while slow.next:
slow = slow.next
stack.append(slow.val)
# 3. Comparison
while stack:
if stack.pop() != cur.val:
return False
cur = cur.next
return True
def is_palindrome_dict(head):
if not head or not head.next:
return True
d = {}
pos = 0
while head:
if head.val in d.keys():
d[head.val].append(pos)
else:
d[head.val] = [pos]
head = head.next
pos += 1
checksum = pos - 1
middle = 0
for v in d.values():
if len(v) % 2 != 0:
middle += 1
else:
step = 0
for i in range(0, len(v)):
if v[i] + v[len(v) - 1 - step] != checksum:
return False
step += 1
if middle > 1:
return False
return True
